DZY 's BLOG

树上的Nim取石子游戏。

说白了就是，维护一棵树，支持：修改点权，询问一条路径上点权的xor值是否为零。

可以用树链剖分做。但是介于n和q都50w这么大感觉常数很DT。。

既然它只修改点的话，影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。

先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零，然后再修改。

(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。

没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define YES *o++='Y',*o++='e',*o++='s',*o++='\n'
#define NO *o++='N',*o++='o',*o++='\n'
const int maxn=500100,maxm=1000100;
int p[maxm],n1[maxm],h[maxn],begin[maxn],end[maxn],bit[maxm],st[maxn],a[maxn],n,ee=0,tot=0;
int anc[maxn][20],dep[maxn];	char buf[25000000],*o=buf,*pt=buf;
inline int getint(){
    int s=0;	while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; 
	return s;
}inline char getop(){
	while(*pt!='Q'&&*pt!='C')	pt++;	return *pt++;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}inline void dfs(int s){
	int top=0;
	begin[st[++top]=s]=dep[s]=++tot;
	while(top){
		int u=st[top],f=0;
		for(int i=h[u];~i;i=n1[i]){
			if(!~begin[p[i]]){
				begin[p[i]]=++tot;
				anc[p[i]][0]=u;
				dep[p[i]]=dep[u]+1;
				st[++top]=p[i];
				h[u]=n1[i];
				f=1;
				break;
			}
		}if(!f){
			end[u]=++tot;
			top--;
		}
	}
}inline int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		j++,k>>=1;
	}if(u==v)	return u;
	for(int j=19;~j;j--)
		if(anc[u][j]!=anc[v][j])	u=anc[u][j],v=anc[v][j];
	return anc[u][0];
}inline void modify(int i){
	for(int x=begin[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
	for(int x=end[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
}inline int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r^=bit[x];
	return r;
}int main(){
	fread(buf,1,25000000,stdin);
	n=getint();
	for(int i=1;i<=n;i++)	a[i]=getint();
	memset(h,-1,sizeof(h));
	memset(begin,-1,sizeof(begin));
	for(int i=1;i<n;i++)	ae(getint(),getint());
	dfs(1);
	for(int i=1;i<=n;i++)	modify(i);
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int q=getint(),x,y,z;
	while(q--){
		if(getop()=='Q'){
			x=getint();y=getint();
			if(ask(begin[x])^ask(begin[y])^a[lca(x,y)])	YES;
			else	NO;
		}else{
			x=getint();y=getint();
			modify(x);
			a[x]=y;
			modify(x);
		}
	}return fwrite(buf,1,o-buf,stdout),0;
}

给你一颗无根树。每条边的路径长是1。

每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。

看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据，发现求的点一定在其中两个点的LCA。

那么就好了。每次求出3个LCA。然后枚举。算出距离和。

介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。

如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char buf[21000000],*pt=buf,*o=buf;
int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0};
int lg[500005],a[500005][20],n,m,tot=1;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++;
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void print(int x){
    char str[11],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}inline void pre(){
    int s=0,e=1; q[0]=1; d[1]=1; v[1]=1;
    while(s<e){
        for(int i=h[q[s++]];i;i=n1[i]) if(!v[p[i]])
            v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1];
    }for(int j=1;j<20;j++) for(int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1];
}inline int lca(int u,int v){
    if(d[u]>d[v]){ u^=v; v^=u; u^=v;}
    int k=d[v]-d[u],j=0; while(k){ if(k&1)v=a[v][j]; j++; k>>=1;}
    if(u==v)return u;
    for(int i=lg[d[u]-1];~i;i--)
        if(a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i];
    return a[u][0]; 
}int main(){
    fread(pt,1,21000000,stdin);  
    n=getint();m=getint();
    for(int i=0;(1<<i)<=n;i++)
        for(int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i;
    int u,v,w,a1,a2,a3,a4,a5,An1,An2;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); 
    pre();
    for(int i=1;i<=m;i++){
        u=getint(),v=getint(),w=getint();
        a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w];
        An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1);
        if((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2;
        if((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3;
        print(An1);*o++=' ';print(An2);*o++='\n';
    }return fwrite(buf,1,o-buf,stdout),0;
}