题解：P8994 [北大集训 2021] 经典游戏
under_the_time
·
2025-12-19 10:19:33
·
题解
题意
给定一棵 n 个点的无根树，第 i 个点上有 a_i 个棋子。假设将这棵树定根在 root 节点上，A 和 B 进行博弈，A 先手。A 先选择是否移动根节点，如果要移动则选择一个与 root 相连的节点作为新节点；随后 B 需要选择一个点将它的棋子数加一。之后两人轮流选择一枚在非叶子节点上的棋子，将它移到所在节点的子树中的任意一点上（不能不移动），无法操作的人输。
$n,Q\le 10^6$，$a_i\le 10^9$。
## 题解
考虑棋子与棋子之间的移动是独立的，可以看成若干个互不影响的子游戏，那么整个游戏的 sg 值就是这些子游戏的 sg 值的异或和，而一个子游戏就形如整棵树只有一枚棋子的 sg 值。当根节点为 $root$、棋子在 $u$ 上时，容易发现其 sg 值就是以 $root$ 为根时 $u$ 到子树内最深的叶子节点路径上边的数量 $len_{root}(u)$。因此根节点为 $root$ 时整个游戏的 sg 值就可以写成
$$
f(root)=\operatorname{xor}_{i=1}^{n}[a_i\text{ is odd}]len_{root}(i)
$$
考虑后手增加的棋子，相当于选择一个点将 $a_i$ 的奇偶性翻转，效果就是使 $f(root)$ 异或上 $len_{root}(i)$。所以先手选择 $root$ 为根有必胜策略，当且仅当 $f(root)$ 不等于任何一个 $len_{root}(i)$，即 $f(root)>\max_ilen_{root}(i)=len_{root}(root)$。
接下来我们需要支持：翻转一个 $a_x$ 的奇偶性，查询 $y$ 及其邻域中满足 $f(root)>len_{root}(root)$ 的点的数量。考虑将 $1$ 定为原树的根，则修改 $a_x$ 时对于所有不在 $x$ 子树内的点 $u$，$f(u)$ 会异或上 $x$ 到 $x$ 子树内最深点的距离 $len_1(x)$；对于在 $x$ 子树内的点 $u$，记 $x$ 到子树外最远点的距离为 $l_1$，到子树内的最远点和次远点的距离分别为 $l_2,l_3$，有两种情况：
- 若 $u$ 在 $x$ 到最深叶节点的路径上走的儿子 $way_x$ 的子树里，且 $u\ne x$，则异或上 $\max(l_1,l_3)$；
- 否则异或上 $\max(l_1,l_2)$。
总之可以分成三个部分：对 $way_x$ 的子树异或 $\max(l_1,l_3)$，对于 $x$ 剩下的子树异或 $\max(l_1,l_2)$，对于整棵树剩下的部分异或 $len_1(x)$。这可以用树状数组在 dfs 序上做区间异或做到。
现在考虑邻域查询。暴力判断 $y$ 和 $y$ 的父亲是否合法后，问题变成统计儿子合法的个数。注意到对于 $(u,v)$ 这条边，满足 $|len_u(u)-len_v(v)|\le 1$，因此 $y$ 的所有儿子的 $len$ 不超过三种。考虑对儿子按照三种 $len$ 分类，对同一类的儿子一起算答案。
考虑每个点对每类儿子维护一个高位到低位的 01Trie 表示所有儿子的 sg 值，当发生子树修改时我们不去暴力更改每棵 Trie，而是改成对子树打一个标记，$tag_u$ 就表示 $u$ 的三棵 01Trie 中的值都需要再异或上 $tag_u$，01Trie 优良的结构使得它支持查询所有数异或一个数后大于某个值的数量。这样做的问题就是在修改 $u$ 的子树时 $u$ 对 $fa_u$ 的贡献会出问题，此时暴力删掉原来的 $f(u)\oplus tag_{fa_u}$ 插入新的 $f'(u)\oplus tag_{fa_u}$ 即可。
时间复杂度 $O(n\log n)$。
## 代码
```cpp
#include<bits/stdc++.h>
bool MemoryST;using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define lowbit(x) ((x)&(-(x)))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define BCNT __builtin_popcount
#define cost_time (1e3*clock()/CLOCKS_PER_SEC)<<"ms"
#define cost_space (abs(&MemoryST-&MemoryED)/1024.0/1024.0)<<"MB"
const int inf=0x3f3f3f3f;
const ll linf=1e18;
mt19937 rnd(random_device{}());
template<typename T>void chkmax(T&x,T y){x=max(x,y);}
template<typename T>void chkmin(T&x,T y){x=min(x,y);}
template<typename T>T abs(T x){return(x<0)?-x:x;}
#if(defined(_WIN32)||defined(_WIN64))
#define fread _fread_nolock
#define fwrite _fwrite_nolock
#else
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define SuperIO
namespace FastIO_SuperGetcharPutchar{
const int LENGTH=1<<21;
char ibuf[LENGTH],obuf[LENGTH],*p1,*p2,*p3=obuf,*p4=obuf+LENGTH-1;
inline void sp_flush(){fwrite(obuf,1,p3-obuf,stdout),p3=obuf;}
inline char sp_getchar(){
if(p1==p2){
p2=(p1=ibuf)+fread(ibuf,1,LENGTH,stdin);
return p1==p2?EOF:*p1++;
} return *p1++;
} inline void sp_putchar(const char &x){*p3++=x;if(p3==p4)sp_flush();}
struct FLUSH{~FLUSH(){sp_flush();}}HSULF;
}
#define getchar FastIO_SuperGetcharPutchar::sp_getchar
#define putchar FastIO_SuperGetcharPutchar::sp_putchar
#ifndef SuperIO
#if(defined(_WIN32)||defined(_WIN64))
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#endif
namespace FastIO_Plus{
inline int read(){
char c=getchar();int f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
int s=0;for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^48);
return s*f;
}inline ll lread(){
char c=getchar();int f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
ll s=0;for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^48);
return s*f;
}inline void read(char&c){c=getchar();}
inline void read(float&x){scanf("%f",&x);}
inline void read(double&x){scanf("%lf",&x);}
inline void read(long double&x){scanf("%Lf",&x);}
inline void read(char*s){
int n=0;for(char c=getchar();c!=EOF&&c!='\n'&&c!=' ';c=getchar())s[n++]=c;
s[n]='\0';
}template<typename T>inline void read(T&x){
char c=getchar();T f=T(1);
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=T(-1);
for(x=T(0);c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
}template<typename T,typename...Arp>inline void read(T&x,Arp&...arp){read(x),read(arp...);}
const int LENGTH=(1<<7);char stk[LENGTH];int top;
inline void write(const char&c){putchar(c);}
inline void write(const char*s){int len=strlen(s);for(register int i=0;i<len;i++)putchar(s[i]);}
template<typename T>inline void write(T val){
if(val==0)return putchar('0'),void(0);
if(val<0)putchar('-'),val=-val;
for(top=0;val>0;stk[top++]=val%10+'0',val/=10);
for(;top;putchar(stk[--top]));
}template<typename T,typename...Arp>inline void write(T x,Arp...arp){write(x),write(arp...);}
}using FastIO_Plus::read,FastIO_Plus::write;
const int maxn=1e6+5;
int score,n,Q,a[maxn];struct Edge{int to,nxt;}e[maxn<<1];int head[maxn],ecnt;
void addEdge(int u,int v){e[++ecnt]=Edge{v,head[u]},head[u]=ecnt;}
pair<int,int>len_in[maxn];int len_out[maxn],len[maxn],fa[maxn];
struct Node{int son[2],siz;Node(){son[0]=son[1]=siz=0;}}T[maxn*23];
int ncnt,bin[maxn*23],top,root[maxn][3],way[maxn],dfn[maxn],siz[maxn],clo;
int getnode(){return top?T[bin[top]]=Node(),bin[top--]:++ncnt;}
void insert(int cur,int val){
for(int i=22;~i;i--){
int p=(val>>i)&1;
if(!T[cur].son[p])T[cur].son[p]=getnode();
T[cur].siz++,cur=T[cur].son[p];
}T[cur].siz++;
}void remove(int cur,int val){
T[cur].siz--;
for(int i=22;~i;i--){
int p=(val>>i)&1,nxt=T[cur].son[p];
if((--T[nxt].siz)==0)bin[++top]=T[cur].son[p],T[cur].son[p]=0;
cur=nxt;
}
}
void dfs(int u,int fa){
len_in[u]=mk(0,0),way[u]=0,siz[u]=1,dfn[u]=++clo,::fa[u]=fa;
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].to)!=fa){
dfs(v,u),siz[u]+=siz[v];int cur=len_in[v].first+1;
if(cur>len_in[u].first)way[u]=v,len_in[u].second=len_in[u].first,len_in[u].first=cur;
else if(cur>len_in[u].second)len_in[u].second=cur;
}
}void dfs2(int u,int fa){
if(fa)len_out[u]=max(len_out[fa]+1,len_in[fa].first==len_in[u].first+1?len_in[fa].second+1:len_in[fa].first+1);
else len_out[u]=0;
len[u]=max(len_in[u].first,len_out[u]);
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].to)!=fa)dfs2(v,u),insert(root[u][len[v]-len[u]+1],0);
}struct BIT{
int b[maxn];
BIT(){memset(b,0,sizeof(b));}
void add(int i,int x){
for(;i<=n;i+=lowbit(i))
b[i]^=x;
}int ask(int i){int res=0;for(;i;i-=lowbit(i))res^=b[i];return res;}
}f,tag;
void mdf(int u,int val){
// cerr<<u<<' '<<val<<'\n';
if(val==0)return;
tag.add(dfn[u],val),tag.add(dfn[u]+siz[u],val);
if(u!=1){
int r=f.ask(dfn[u]),p=tag.ask(dfn[fa[u]]);
remove(root[fa[u]][len[u]-len[fa[u]]+1],r^p);
insert(root[fa[u]][len[u]-len[fa[u]]+1],r^val^p);
}f.add(dfn[u],val),f.add(dfn[u]+siz[u],val);
}void rev(int u){
int l1=len_out[u],l2=len_in[u].first,l3=len_in[u].second;
mdf(1,l2),mdf(u,l2^max(l1,l2));
if(way[u])mdf(way[u],max(l1,l2)^max(l1,l3));
}int chk(int u){return f.ask(dfn[u])>len[u];}
int query(int cur,int lim,int mov){
int ans=0;
for(int i=22;~i;i--){
int p=(lim>>i)&1,q=(mov>>i)&1;
if(p==0&&T[cur].son[q^1])ans+=T[T[cur].son[q^1]].siz;
if(!T[cur].son[p^q])return ans;
cur=T[cur].son[p^q];
}return ans;
}
bool MemoryED;int main(){
read(score,n,Q);for(int i=1,u,v;i<n;i++)read(u,v),addEdge(u,v),addEdge(v,u);
for(int i=1;i<=n;i++)a[i]=read()&1,root[i][0]=getnode(),root[i][1]=getnode(),root[i][2]=getnode();
dfs(1,0),dfs2(1,0);for(int i=1;i<=n;i++)if(a[i])rev(i);
// for(int i=1;i<=n;i++)cerr<<way[i]<<" \n"[i==n];
// for(int i=1;i<=n;i++)cerr<<f.ask(dfn[i])<<" \n"[i==n];
for(int _=1,x,y;_<=Q;_++){
read(x,y),rev(x);
int cnt=chk(y)+(y==1?0:chk(fa[y])),tg=tag.ask(dfn[y]);
for(int d=-1;d<=1;d++)cnt+=query(root[y][d+1],len[y]+d,tg);
write(cnt,'\n');
}
return 0;
}
```