洛谷 P5556 圣剑护符 题解

题目概括：

给定一棵n nn个节点的树，每个节点有一个初始权值v i v_ivi​（范围为[ 0 , 2 30 ) [0, 2^{30})[0,230)）。需要处理q qq
次操作，操作分为两种：

1. 修改操作Update x y z：将节点x xx到y yy的简单路径上所有节点的权值异或上z zz。
2. 查询操作Query x y：询问从节点x xx到y yy的简单路径上的所有节点权值组成的集合中，是否存在两个不相等的子集（子集指节点集合的子集，空集也包含在内），使得这两个子集中所有节点权值的异或和相等。如果存在输出
   YES，否则输出NO。

问题等价于：判断路径上的所有节点权值在异或意义下是否线性相关（即是否存在一个非空子集的异或和为0 00）。由于权值位数不超过30 3030，若路径长度大于30 3030，根据鸽巢原理必然线性相关，答案一定为YES；否则需要实际检查这些权值是否线性相关。
From DeepSeek

简单来说，你需要实现的是：对于一颗树，你需要实现快速的单链异或+单点查询。

那我们如果想快速完成操作，就想到把修改的东西放到一个区间内，用线段树维护这样一段区间的复杂度时O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)的。那如何把一条链放到一个区间内呢？

树链剖分！

考虑一下，如果我们在进行重链剖分的同时计算 DFS 序，那么同一条重链上的结点的时间戳一定是连续的。

所以修改的时候，我们用类似求 LCA 的方法进行操作，每次更新这条重链时间戳所对应的区间，然后跳到当前链链头的父亲。

这样我们就在O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)处理了一个区间，而树链剖分在最坏情况下会有log ⁡ 2 n \log_2 nlog2​n个区间，所以插入的时间复杂对时O ( log ⁡ 2 2 n ) O(\log_2^2n)O(log22​n)级别的。

考虑查询。这里用到一个 trick。如果集合的规模很大，那么答案必然有解。这道题，树上所有结点的权值小于2 30 2^{30}230，这意味着如果在31 3131个里面选择一些，一共有2 31 2^{31}231种方案，根据抽屉原理，必然有一种满足要求的方案。

对于l e n ≤ 30 len \le 30len≤30的部分来说，考虑异或空间线性基的性质，显然基中不能出现异或值为0 00的数。这意味着有两个方法表示同一个数。故一定有方法使两个子集的异或和相同。

#include<bits/stdc++.h>#definels(p<<1)#definers(p<<1|1)usingll=longlong;constexprintN=1e5+5;std::vector<int>adj[N];structSegment_Tree{structNode{intnum,l,r;inttag;}t[N<<2];voidbuild(intp,intpl,intpr){t[p].l=pl;t[p].r=pr;t[p].num=t[p].tag=0;if(pl==pr)return;intmid=pl+pr>>1;build(ls,pl,mid);build(rs,mid+1,pr);}voidpush_down(intp){if(t[p].tag){t[ls].tag^=t[p].tag;t[ls].num^=t[p].tag;t[rs].tag^=t[p].tag;t[rs].num^=t[p].tag;t[p].tag=0;}}voidupdate(intp,intl,intr,intval){if(t[p].l>r||t[p].r<l)return;if(l<=t[p].l&&t[p].r<=r){t[p].num^=val;t[p].tag^=val;return;}push_down(p);update(ls,l,r,val);update(rs,l,r,val);}intquery(intp,intpos){if(t[p].l==t[p].r)returnt[p].num;push_down(p);intmid=t[p].l+t[p].r>>1;if(pos<=mid)returnquery(ls,pos);elsereturnquery(rs,pos);}voidprint(intp){if(t[p].l==t[p].r)std::cout<<t[p].num<<" ";elsepush_down(p),print(ls),print(rs);}}tree;intfa[N],dep[N],siz[N],top[N],dfn[N],v[N];inttim;voiddfs1(intu,intf){fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;for(intv:adj[u]){if(v!=f){dfs1(v,u);siz[u]+=siz[v];}}}voiddfs2(intu,intf){top[u]=f;dfn[u]=++tim;intmx=-1,s=-1;tree.update(1,tim,tim,v[u]);for(intv:adj[u]){if(v!=fa[u]&&siz[v]>mx){mx=siz[v];s=v;}}if(s!=-1)dfs2(s,f);for(intv:adj[u]){if(v!=fa[u]&&v!=s)dfs2(v,v);}}voidupdate(intx,inty,intval){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])std::swap(x,y);tree.update(1,dfn[top[x]],dfn[x],val);x=fa[top[x]];}if(dfn[x]>dfn[y])std::swap(x,y);tree.update(1,dfn[x],dfn[y],val);}intlca(intu,intv){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])v=fa[top[v]];elseu=fa[top[u]];}if(dep[u]<dep[v])returnu;returnv;}constexprintM=31;structleaner_basis{intb[M];voidinit(){memset(b,0,sizeofb);}boolinsert(intx){for(inti=M-1;i>=0;i--){if(!(x&(1<<i)))continue;if(!b[i]){b[i]=x;return1;}x^=b[i];}returnfalse;}}basis;intn,q,x,y,z;intmain(){std::cin>>n>>q;for(inti=1;i<=n;i++)std::cin>>v[i];for(inti=1;i<n;i++){intu,v;std::cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}tree.build(1,1,n);dfs1(1,0);dfs2(1,1);while(q--){std::string s;std::cin>>s>>x>>y;if(s[0]=='U'){std::cin>>z;update(x,y,z);}else{intl=lca(x,y);intdis=dep[x]+dep[y]-2*dep[l]+1;if(dis>30)std::cout<<"YES\n";else{basis.init();boolflag=false;if(!basis.insert(tree.query(1,dfn[l])))flag=1;if(!flag)while(x!=l){if(!basis.insert(tree.query(1,dfn[x]))){flag=1;break;}x=fa[x];}if(!flag)while(y!=l){if(!basis.insert(tree.query(1,dfn[y]))){flag=1;break;}y=fa[y];}std::cout<<(flag?"YES\n":"NO\n");}}}}