A – 异或粽子

“傻逼题。”——XG_Zepto

这道题还是挺好做的，先把所有前缀异或和放入 Trie 树中，然后\(O(n)\)枚举右端点\(r\)，在 Trie 树中查找与前缀异或和\([1-r]\)异或的最大值并放入堆中（放入堆时标记好排名为\(1\)）。之后在堆中取出，并不停的放入排名逐渐变大的异或和查询值，收集前\(k\)个即可。

// P5283.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5e5 * 35;
struct npair
{
    int point, rk;
    ll val;
    bool operator<(const npair &np) const { return val < np.val; }
};
int trie[MAX_N][2], size[MAX_N], treetot = 1, current_rank;
ll n, k, arr[MAX_N];
priority_queue<npair> pq;
void insert(ll num)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        size[p]++;
        if (trie[p][bit] == 0)
            trie[p][bit] = ++treetot;
        p = trie[p][bit];
    }
    size[p]++;
}
ll atRank(ll num, int rk)
{
    int p = 1;
    ll ans = 0;
    for (int i = 31; i >= 0; i--)
    {
        int bit = ((num >> i) & 1);
        if (trie[p][bit ^ 1] == 0)
            p = trie[p][bit];
        else if (rk <= size[trie[p][bit ^ 1]])
            p = trie[p][bit ^ 1], ans |= 1LL << i;
        else
            rk -= size[trie[p][bit ^ 1]], p = trie[p][bit];
    }
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &k), k *= 2;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), arr[i] = arr[i - 1] ^ arr[i];
    for (int i = 0; i <= n; i++)
        insert(arr[i]);
    for (int i = 0; i <= n; i++)
        pq.push(npair{i, 1, atRank(arr[i], 1)});
    ll ans = 1;
    for (int i = 1; i <= k; i++)
    {
        npair np = pq.top();
        ans += np.val, pq.pop();
        if (np.rk < n)
            np.rk++, np.val = atRank(arr[np.point], np.rk), pq.push(np);
    }
    printf("%lld", ans >> 1);
    return 0;
}

B – 春节十二响

“傻逼题。”——XG_Zepto

这道题很有趣。考虑一个节点有两条儿子链：

我们可以考虑把链放进对应的队列里，然后取出最大值进行一一合并：正好两条链上的点互不为祖先关系，所以保留最大值即可达到合并的作用，筛去一堆无用信息。所以，在\(n\)条链的情况下我们只需要一条一条合并即可（记住，选择短的链进行合并，如果链的长度比当前堆内元素个数大小要大，可以考虑 O(1) 交换堆做到更优的复杂度。

// P5290.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 2000;
int fa[MAX_N], head[MAX_N], current, weight[MAX_N], n, size[MAX_N];
int dfn[MAX_N], tot, tmp[MAX_N];
priority_queue<int> queues[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u)
{
    dfn[u] = ++tot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[u])
        {
            dfs(edges[i].to);
            if (queues[dfn[edges[i].to]].size() > queues[dfn[u]].size())
                swap(dfn[edges[i].to], dfn[u]);
            int m = queues[dfn[edges[i].to]].size();
            for (int pt = 1; pt <= m; pt++)
            {
                tmp[pt] = max(queues[dfn[u]].top(),
                              queues[dfn[edges[i].to]].top());
                queues[dfn[edges[i].to]].pop();
                queues[dfn[u]].pop();
            }
            for (int pt = 1; pt <= m; pt++)
                queues[dfn[u]].push(tmp[pt]);
        }
    queues[dfn[u]].push(weight[u]);
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &weight[i]);
    for (int i = 2; i <= n; i++)
        scanf("%d", &fa[i]), addpath(fa[i], i), addpath(i, fa[i]);
    dfs(1);
    long long ans = 0;
    while (!queues[dfn[1]].empty())
        ans += queues[dfn[1]].top(), queues[dfn[1]].pop();
    printf("%lld", ans);
    return 0;
}