[20220214联考] 树上的棋局
前言
这种才6k、200行出头的代码不是随便调一调就调过了吗。【战术后仰】
但是会不会做就是另外一回事了。
题目
给一棵 \(n\) 个点的树，初始时根为 \(1\)，每个节点上有个棋子。然后 Vi 和 Powder 开始博弈，博弈的规则很简单，每个人在她的轮次时可以将某个棋子移到该棋子所在节点的子树内任意一点(显然不能是这个点本身)。
但是这个典中典问题两人都很明白是 \(\tt SG\) 函数板题，所以她们又加入了 \(m\) 个奇怪的操作：
- \(u,v,x\) 表示在 \(u,v\) 的路径上各放一个棋子，并把根换为 \(x\)。
- \(u,x\) 表示在 \(u\) 及其子树内的节点各放一个棋子(注意此时的树根)，并把根换为 \(x\)。
两人在祖安混了这么久，当然很懂博弈，于是她们想问你更本质的东西：此时的 \(\tt SG\) 函数值，而非先后手谁胜。
\(1\le n\le 2\times 10^5;0\le m\le 2\times 10^5.\)
讲解
由于把题错看成移动棋子是移动到某个儿子上而直接自闭去刚T1(然后被卡科技了)。
在没看错题的情况下，只要你稍微懂点 \(\tt SG\) 函数，我们就可以得出结论，每个节点的 \(\tt SG\) 函数值为该点到其子树内点的最大距离。显然同一个位置的 \(2\) 个棋子的 \(\tt SG\) 函数值为 \(0\)，我们只需维护 \(0/1\) 值表示是否需要统计贡献。
对于换根操作其实有个经典解决办法(然而我不知道qwq)：单独处理新根到原根路径上的贡献，其它点的贡献其实是不变的，可以直接用原来的。当然这个贡献要只和自己的子树有关才能这么做，而这道题满足条件。
考虑这条链怎么求贡献，卷爷说：直接重链剖分。
然后我们考虑跳重链的时候怎么求贡献，其实直接预处理每个节点当树根在其重儿子子树内时其 \(\tt SG\) 函数值即可。
但实际上我们预处理的是 \(fSG_i:i\) 为根时其父亲的 \(SG\) 函数值，预处理这个是因为跳轻边的时候也要用。
由于向上跳轻边只有 \(\log_2n\) 级别个，可以直接暴力做。
总时间复杂度 \(O(n\log_2^2n)\)。
代码
就这？完全不够写啊！
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 200005;
int n,m,rt = 1;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot;
struct edge
{
int v,nxt;
}e[MAXN<<1];
void Add_Edge(int x,int y)
{
e[++tot] = edge{y,head[x]};
head[x] = tot;
}
void Add_Double_Edge(int x,int y)
{
Add_Edge(x,y);
Add_Edge(y,x);
}
int d[MAXN],siz[MAXN],f[MAXN],MAX[MAXN][2],fSG[MAXN],son[MAXN];
//depth son_size father MAX0,1 father's SG heavy son(poor English
void dfs1(int x,int fa)
{
d[x] = d[fa] + 1; siz[x] = 1; f[x] = fa;
for(int i = head[x],v; i ;i = e[i].nxt)
if((v = e[i].v) ^ fa)
{
dfs1(v,x),siz[x] += siz[v];
if(siz[v] > siz[son[x]]) son[x] = v;
if(MAX[v][0]+1 > MAX[x][0]) MAX[x][1] = MAX[x][0],MAX[x][0] = MAX[v][0]+1;
else if(MAX[v][0]+1 > MAX[x][1]) MAX[x][1] = MAX[v][0]+1;
}
}
int dfn[MAXN],rdfn[MAXN],dfntot,tp[MAXN];
void dfs2(int x,int t)
{
tp[x] = t; rdfn[dfn[x] = ++dfntot] = x;
if(f[x] > 1) fSG[x] = Max(fSG[x],fSG[f[x]]+1);
if(!son[x]) return;
if(MAX[son[x]][0]+1 == MAX[x][0]) fSG[son[x]] = MAX[x][1];
else fSG[son[x]] = MAX[x][0];
dfs2(son[x],t);
for(int i = head[x],v; i ;i = e[i].nxt)
if(((v = e[i].v) ^ f[x]) && (v ^ son[x]))
{
if(MAX[v][0]+1 == MAX[x][0]) fSG[v] = MAX[x][1];
else fSG[v] = MAX[x][0];
dfs2(v,v);
}
}
#define lc (x<<1)
#define rc (x<<1|1)
int SG[MAXN<<2],ASG[MAXN<<2];//SG & all SG
int ESG[MAXN<<2],AESG[MAXN<<2];//except heavy son's SG -> ESG
bool lz[MAXN<<2];//lazy tag
void calc(int x){lz[x] ^= 1; SG[x] ^= ASG[x]; ESG[x] ^= AESG[x];}
void up(int x)
{
SG[x] = SG[lc] ^ SG[rc];
ESG[x] = ESG[lc] ^ ESG[rc];
}
void down(int x)
{
if(!lz[x]) return;
calc(lc); calc(rc);
lz[x] = 0;
}
void Build(int x,int l,int r)
{
if(l == r) {ASG[x] = SG[x] = MAX[rdfn[l]][0];ESG[x] = AESG[x] = fSG[son[rdfn[l]]];return;}
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
up(x); ASG[x] = ASG[lc] ^ ASG[rc]; AESG[x] = AESG[lc] ^ AESG[rc];
}
void Add(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) {calc(x);return;}
int mid = (l+r) >> 1; down(x);
if(ql <= mid) Add(lc,l,mid,ql,qr);
if(mid+1 <= qr) Add(rc,mid+1,r,ql,qr);
up(x);
}
bool Querylz(int x,int l,int r,int pos)
{
if(l == r) return lz[x];
int mid = (l+r) >> 1; down(x);
if(pos <= mid) return Querylz(lc,l,mid,pos);
else return Querylz(rc,mid+1,r,pos);
}
int QuerySG(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) return SG[x];
int mid = (l+r) >> 1,ret = 0; down(x);
if(ql <= mid) ret ^= QuerySG(lc,l,mid,ql,qr);
if(mid+1 <= qr) ret ^= QuerySG(rc,mid+1,r,ql,qr);
return ret;
}
int QueryESG(int x,int l,int r,int ql,int qr)
{
if(ql > qr) return 0;
if(ql <= l && r <= qr) return ESG[x];
int mid = (l+r) >> 1,ret = 0; down(x);
if(ql <= mid) ret ^= QueryESG(lc,l,mid,ql,qr);
if(mid+1 <= qr) ret ^= QueryESG(rc,mid+1,r,ql,qr);
return ret;
}
void Add_Chain(int u,int v)
{
while(tp[u] ^ tp[v])
{
if(d[tp[u]] < d[tp[v]]) swap(u,v);
Add(1,1,n,dfn[tp[u]],dfn[u]);
u = f[tp[u]];
}
if(d[u] > d[v]) swap(u,v);
Add(1,1,n,dfn[u],dfn[v]);
}
void Add_SonTree(int x)//pot 3
{
int now = rt;
if(x == now) {Add(1,1,n,1,n);return;}//pot 4
while(d[now] > d[x] && tp[now] != tp[x]) now = f[tp[now]];
if(tp[now] != tp[x] || d[now] < d[x]) Add(1,1,n,dfn[x],dfn[x]+siz[x]-1);
else
{
now = rt;
while(f[now] != x && tp[now] != tp[x])
{
now = tp[now];
if(f[now] ^ x) now = f[now];
}
if(tp[now] == tp[x]) Add(1,1,n,dfn[son[x]],dfn[son[x]]+siz[son[x]]-1);
else Add(1,1,n,dfn[now],dfn[now]+siz[now]-1);
Add(1,1,n,1,n);
}
}
int solve()
{
int ret = SG[1],now = rt;
while(tp[now] ^ 1)
{
ret ^= QuerySG(1,1,n,dfn[tp[now]],dfn[now]);
now = f[tp[now]];
}
ret ^= QuerySG(1,1,n,1,dfn[now]); now = rt;
//从这里开始要保证now的贡献是算了的
if(!Querylz(1,1,n,dfn[now])) ret ^= Max(MAX[now][0],now == 1 ? 0 : fSG[now]+1);//itself pot1,pot5,pot6(一个位置锅三次是我没想到的
while(tp[now] ^ 1)
{
ret ^= QueryESG(1,1,n,dfn[tp[now]],dfn[now]-1); now = tp[now];
if(!Querylz(1,1,n,dfn[f[now]])) ret ^= fSG[now]; now = f[now];
}
ret ^= QueryESG(1,1,n,dfn[tp[now]],dfn[now]-1);//pot2
return ret;
}
int tmp[MAXN];
void print(int x,int l,int r)
{
if(l == r) {tmp[rdfn[l]] = lz[x];return;}
int mid = (l+r) >> 1; down(x);
print(lc,l,mid); print(rc,mid+1,r);
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = Read(); m = Read();
for(int i = 1;i < n;++ i) Add_Double_Edge(Read(),Read());
dfs1(1,0); dfs2(1,1);
Build(1,1,n);
while(m --> 0)
{
if(Read() == 1) Add_Chain(Read(),Read()),rt = Read();
else Add_SonTree(Read()),rt = Read();
Put(solve(),'\n');
}
return 0;
}