[NOI Simulation Competition] Paper Tiger Game (Game Theory SG Function, Long Chain Division)

题面

某天,C 和 K 觉得很无聊,So I decided to play a classic little game：

在一棵有 $n$ on a rooted tree of nodes,标号为 $i$ 的节点上有 $a_i$ 个棋子.Players take turns during the game,Any node can be set at a time $u$ Place a pawn from the top to any point $v\in U(u)$ 上,其中 $U(u)=subtree\{u\}-\{u\}$,表示 $u$ 的子树内（不包含 $u$ 本身）的点组成的集合.An operator failure cannot be performed.

The two think,It might be fun to give each person a special ability：

C 在开始游戏之前,可以选择Will be the root of the current tree $R$ switch to with $R$ any adjacent point $R^{\prime }$ 上.Defines that two points are adjacent if and only if the two points are directly connected by an edge.

K 在开始游戏之前,必须选择树上的一个节点,Add a pawn on top.

C 和 K Decided to play $m$ 局游戏.The flow of each game is as follows：

1. 游戏开始前,C 和 K will be negotiated,First labelled as $x$ Put a pawn on the node,Then set the root to $y$.
2. 之后 C You can choose whether to activate special abilities,C 决策完之后 K You can choose whether to activate special abilities.
3. After the decision of the special ability is over,A round will be played on this tree C 先手、K Backhand game.After the game is completed, the state of the pieces on the tree will be displayedRevert to process 1 结束后的状态.

由于 C 和 K 都是纸老虎,After the decision is over it is enough to know who will win,I don't want to actually start it .于是 C Decided to test you：C During the second step of each game,It doesn't matter how many ways there are decisions K How to perform special abilities,Both exist when starting the game必胜策略？The two decisions are made differently,当且仅当两种决策Replaced tree roots$R^{\prime }$不同,或者Only one of the two does not activate special abilities.

输入格式

第一行包括一个整数,Indicates the score of the subtask in which the test point is located.You can use this information to determine the special properties that the test point satisfies.特别的,This line is used in the sample download $0$ 代替.

The second line contains two positive integers separated by spaces $n,m$,Indicates the number of nodes in the tree and the number of rounds of the game.Nodes on the tree from $1$ 到 $n$ 编号.

接下来 $n-1$ 行,每行包含两个用空格隔开的正整数 $u_i,v_i$,满足 $1\le u_i,v_i\le n$,表示编号为 $u_i$ 和 $v_i$ The nodes are directly connected by edges.

接下来一行包含 $n$ 个用空格隔开的整数 $a_1,a_2,...,a_n$,满足 $0\le a_1,a_2,...,a_n\le 10^9$.

接下来 $m$ 行,每行包含两个用空格隔开的正整数 $x,y$ Describe a game,满足 $1\le x,y\le n$.

输出格式

你需要输出 $m$ 行,其中第 $i$ Line should contain a non-negative integer $x$ 表示第 $i$ 局游戏中,C How many decision-making scenarios exist for using special abilities,使得 C There is a sure-win strategy in this game.注意,Does not use special abilities也是一种可能可行的决策方案.

题解

First of all, conclusions can be drawn：A chess piece is placed at the root node of a tree SG The function is equal to the height of this tree.

然后,A point is the root“可行”当且仅当 SG The value is greater than the tree height,Because there is no way to make it by adding a point SG 归零.

于是,The brute force method is to directly enumerate the root modification contributions for each modification,The query enumerates adjacencies.

So we need to quickly modify the contribution next,As well as fast query adjacencies.

We record the longest and second longest paths from each point,will find no matter where the root is,The contribution of this point is either the longest path or the second longest path,And the contribution is the second longest path if and only if the root is in the direction of the longest path.所以修改只需要支持子树修改.用DFS序+A line segment tree is fine.

If we do a long chain segmentation of the tree,A point will be found $x$ 的轻儿子The tree height is the same when it is the root,都等于 $x$ 的最长路径+1 .于是,我们只需要用trieThe tree maintains all light sons SG 值.Use an overall XORtag,This can be done when the subtree is modified $O(\log )$ .

To find the longest path and the second longest path, change the rootDP就好了.

总时间复杂度 $O(n\log n)$ ,空间 $O(n\log n)$ Node recycling is required.

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 1000005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
#define SQ 317
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
#define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int a[MAXN];
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],cne;
void ins(int x,int y) {
    
	nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}

struct it{
    
	PR a,b;
	it(){
    a=b={
    0,0};}
}dp[MAXN],dp2[MAXN],pr[MAXN],sf[MAXN];
it merg(it x,it y) {
    
	it z; z.a = max(x.a,y.a);
	z.b = max(x.b,y.b);
	if(x.a.SE != z.a.SE) z.b = max(z.b,x.a);
	if(y.a.SE != z.a.SE) z.b = max(z.b,y.a);
	return z;
}
void dfs(int x,int ff) {
    
	dp[x].a = {
    0,x};
	it p = it();
	stack<int> sn;
	for(int i = hd[x];i;i = nx[i]) {
    
		if(v[i] != ff) {
    
			dfs(v[i],x);
			sn.push(v[i]);
			it nm = dp[v[i]];
			nm.a.FI ++; nm.a.SE = v[i];
			nm.b = {
    0,0};
			dp[x] = merg(dp[x],nm);
			pr[v[i]] = p; pr[v[i]].b = {
    0,0};
			pr[v[i]].a.SE = x;
			p = merg(p,nm);
		}
	}
	p = it();
	while(!sn.empty()) {
    
		int y = sn.top(); sn.pop();
		sf[y] = p; sf[y].b = {
    0,0};
		sf[y].a.SE = x;
		it nm = dp[y]; nm.a.FI ++;
		nm.a.SE = y; nm.b = {
    0,0};
		p = merg(p,nm);
	}
	return ;
}
int fa[MAXN];
int tre[MAXN<<2],M;
void maketree(int n) {
    
	M=1; while(M<n+2) M<<=1;
}
void addseg(int l,int r,int y) {
    
	for(int s=M+l-1,t=M+r+1;(s>>1)^(t>>1);s >>= 1,t >>= 1) {
    
		if(!(s&1)) tre[s^1] ^= y;
		if(t & 1) tre[t^1] ^= y;
	} return ;
}
int findp(int x) {
    
	int as=0,s=M+x;
	while(s)as^=tre[s],s>>=1;
	return as;
}
int dfn[MAXN],rr[MAXN],tim;
void dfs2(int x,int ff) {
    
	fa[x] = ff;
	dp2[x].a = {
    0,x};
	if(ff) {
    
		dp2[x] = merg(dp2[ff],merg(pr[x],sf[x]));
		dp2[x].a.FI ++; dp2[x].a.SE = ff;
		dp2[x].b = {
    0,0};
	}
	dp[x] = merg(dp[x],dp2[x]);
	dfn[x] = ++ tim;
	for(int i = hd[x];i;i = nx[i]) {
    
		if(v[i] != ff) {
    
			dfs2(v[i],x);
		}
	}
	rr[x] = tim;
	return ;
}
int tri[MAXN*25][2],ct[MAXN*25];
stack<int> tra; int cnt = 1;
int newp() {
    
	if(tra.empty()) tra.push(++ cnt);
	int x = tra.top(); tra.pop();
	tri[x][0]=tri[x][1]=ct[x]=0;return x;
}
void ins(int p,int x,int y) {
    
	static int st[55],tp;
	st[tp = 0] = p;
	for(int i = 20;i >= 0;i --) {
    
		int d = (x>>i)&1;
		if(!tri[p][d]) tri[p][d] = newp();
		p = tri[p][d]; ct[p] += y;
		st[++ tp] = p;
	}
	while(tp > 0 && ct[st[tp]] == 0) {
    
		int t = st[tp --];
		int ff = st[tp];
		if(tri[ff][0] == t) tri[ff][0] = 0;
		if(tri[ff][1] == t) tri[ff][1] = 0;
		tra.push(t);
	} return ;
}
int cont(int p,int x,int y) {
    
	int as = 0;
	for(int i = 20;i >= 0;i --) {
    
		int d = (x>>i)&1,d2 = (y>>i)&1;
		if(!d2) as += ct[tri[p][d^1]];
		p = tri[p][d^d2];
	} return as;
}
int sm[MAXN],mxd[MAXN],hv[MAXN],rt[MAXN];
void xorp(int x,int y) {
    
	if(!x) return ;
	int ff = fa[x];
	if(ff && x != hv[ff]) {
    
		int nm = sm[x] ^ findp(dfn[x]) ^ findp(dfn[ff]);
		ins(rt[ff],nm,-1);
		ins(rt[ff],nm^y,1);
	}
	sm[x] ^= y;
	return ;
}
void xortree(int x,int y) {
    
	if(!x) return ;
	int ff = fa[x];
	if(ff && x != hv[ff]) {
    
		int nm = sm[x] ^ findp(dfn[x]) ^ findp(dfn[ff]);
		ins(rt[ff],nm,-1);
		ins(rt[ff],nm^y,1);
	}
	addseg(dfn[x],rr[x],y);
	return ;
}
void addpoint(int x) {
    
	if(hv[x] == fa[x]) {
    
		xortree(1,dp[x].b.FI);
		xortree(x,mxd[x]^dp[x].b.FI);
	}
	else {
    
		xortree(1,mxd[x]);
		xortree(hv[x],mxd[x]^dp[x].b.FI);
	} return ;
}
bool checkp(int x) {
    
	int nm = sm[x] ^ findp(dfn[x]);
	return nm > mxd[x];
}
int main() {
    
	freopen("classic.in","r",stdin);// “典”
	freopen("classic.out","w",stdout);
	int pts = read();
	n = read(); m = read();
	for(int i = 1;i < n;i ++) {
    
		s = read();o = read();
		ins(s,o); ins(o,s);
	}
	for(int i = 1;i <= n;i ++) {
    
		a[i] = read()&1;
	}
	dfs(1,0); dfs2(1,0);
	maketree(n);
	for(int i = 1;i <= n;i ++) mxd[i] = dp[i].a.FI,hv[i] = dp[i].a.SE,rt[i] = newp();
	for(int i = 1;i <= n;i ++) {
    
		if(fa[i] && i != hv[fa[i]]) {
    
			ins(rt[fa[i]],0,1);
		}
	}
	for(int i = 1;i <= n;i ++) {
    
		if(a[i]) {
    
			addpoint(i);
		}
	}
	for(int i = 1;i <= m;i ++) {
    
		s = read();o = read();
		addpoint(s);
		int ans = 0,nm = findp(dfn[o]);
		if((sm[o]^nm) > mxd[o]) ans ++;
		ans += cont(rt[o],nm,mxd[o]+1);
		if(hv[o]) ans += checkp(hv[o]);
		if(fa[o] && fa[o] != hv[o]) ans += checkp(fa[o]);
		AIput(ans,'\n');
	}
	return 0;
}