题解：P17304 [ICPC 2026 Xi'an I] XOR and LCA

· · 题解

题意简述

一棵树的结点编号为 0 到 2^n-1。对每个无序点对 u<v，把根设为 u\mathbin{\oplus}v，求对应最近公共祖先的异或和。

解题思路

先把树固定以 0 为根，用 L(x,y) 表示此时的最近公共祖先。

任取三个结点 a,b,c。L(a,b),L(a,c),L(b,c) 中有两个相等，第三个不浅于它们。把根改成 c 后，a,b 的最近公共祖先正是三者中最深的那个。异或会消去两个相等值，所以：

\operatorname{LCA}_c(a,b)=L(a,b)\mathbin{\oplus}L(a,c)\mathbin{\oplus}L(b,c)

令：

X=\bigoplus_{u<v}L(u,v)

代入 c=u\mathbin{\oplus}v。另外两项在每个无序点对上分别以 u 和 v 为首个参数，合起来就是所有互异有序点对：

Y=\bigoplus_{u\ne v}L(u,u\mathbin{\oplus}v)

固定 u。当 v 遍历除 u 外的全部编号时，u\mathbin{\oplus}v 恰好遍历除 0 外的全部编号。补上缺少的 0 不会改变结果，因为以 0 为根时 L(u,0)=0。因此：

Y=\bigoplus_{u,w}L(u,w)

其中 u\ne w 的每个无序点对出现两次，异或后抵消。对角线满足 L(u,u)=u，所以：

Y=\bigoplus_{u=0}^{2^n-1}u

原问题已经化成固定根下的无序点对 LCA 异或和 X，再异或一次全部结点编号。

下面求 X。设结点 x 的儿子子树大小为 s_1,s_2,\dots,s_k。以 x 为最近公共祖先的互异无序点对分成两类：

只关心总数的奇偶性。设奇数大小的儿子子树共有 q 棵，则：

(\operatorname{siz}_x-1)\bmod2=q\bmod2

第二类中，只有两个子树大小都为奇数时乘积才是奇数。因此，x 需要被异或进 X 的条件是：

\left(q+\binom{q}{2}\right)\bmod2=1

实现时先以 0 为根得到父亲和遍历序。再按逆序处理结点，维护子树大小及奇数儿子数量。一个结点处理完后，把子树大小累加到父亲；若其子树为奇数，再让父亲的奇数儿子数加一。

结点编号 0 到 2^n-1 的异或和在 n=1 时为 1。当 n\ge2 时，每个二进制位都恰好出现偶数次，异或和为 0。

代码使用度数前缀和建立连续邻接表。所有边只需线性装填，遍历和逆序统计也各执行一次。时间复杂度为 O(2^n)，空间复杂度为 O(2^n)。

正确性证明

三点在固定根树上的两两 LCA 中，两个较浅值相等，剩余值最深。改根到第三点后，另外两点的 LCA 就是这个最深值。因此，三项异或恒等式成立。

对另外两项做有序化后，异或映射 v\mapsto u\mathbin{\oplus}v 是结点编号全集上的双射。补入的 w=0 项均为零。全部有序 LCA 中，非对角项成对抵消，只剩所有 L(u,u)=u。故原答案确实等于 X 与全部编号异或和。

固定结点 x 时，最近公共祖先为 x 的点对，要么包含 x，要么分处两个不同儿子子树，分类互斥且完备。第一类数量奇偶等于奇数儿子数，第二类只有任选两棵奇数子树才贡献奇数。程序使用的 q+\binom q2 因而准确给出 x 的出现次数奇偶性。

逆序遍历保证处理 x 时所有儿子子树大小已经求出。程序恰好异或所有出现奇数次的 LCA，再加入编号异或和，所以最终答案正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=(1<<21)+5;
const int M=(1<<22)+5;
int eu[N],ev[N];
int deg[N],st[N],cur[N],e[M];
int fa[N],siz[N],odd[N],q[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int p;
        cin>>p;
        int n=1<<p;
        fill(deg,deg+n,0);
        for(int i=1;i<n;i++)
        {
            cin>>eu[i]>>ev[i];
            deg[eu[i]]++;
            deg[ev[i]]++;
        }
        st[0]=0;
        for(int i=0;i<n;i++)st[i+1]=st[i]+deg[i];
        copy(st,st+n,cur);
        for(int i=1;i<n;i++)
        {
            e[cur[eu[i]]++]=ev[i];
            e[cur[ev[i]]++]=eu[i];
        }
        int m=1;
        q[0]=0;
        fa[0]=-1;
        for(int i=0;i<m;i++)
        {
            int x=q[i];
            for(int j=st[x];j<st[x+1];j++)
            {
                int y=e[j];
                if(y==fa[x])continue;
                fa[y]=x;
                q[m++]=y;
            }
        }
        fill(siz,siz+n,1);
        fill(odd,odd+n,0);
        int ans=p==1;
        for(int i=n-1;i>=0;i--)
        {
            int x=q[i],k=odd[x];
            if((k+k*(k-1)/2)&1)ans^=x;
            if(fa[x]!=-1)
            {
                siz[fa[x]]+=siz[x];
                odd[fa[x]]+=siz[x]&1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}