题意：n个节点的树，每个点有一种颜色。现有m种询问，每次询问x y a b表示x到y的路径上颜色的种数且a颜色看成b颜色。（n<=50000, m<=100000）

dfs序序列分块战术核导弹= =：

#include 
     
      using namespace std;const int N=50005, M=100005;inline int getint() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') (x*=10)+=c-'0', c=getchar(); return x; }int ihead[N], cnt, blo[N], f[N][16], FF[N], LL[N], tot, dep[N], cal[N], pos[N<<1], col[N], st[N], n, m, Ans[M], ans;struct E { int next, to; }e[N<<1];struct Q { int x, y, lca, a, b, id; }q[M];bool cmp(const Q &a, const Q &b) { return blo[a.x]==blo[b.x]?a.y
      
       
        =0; --i) if((d>>i)&1) x=f[x][i]; if(x==y) return x;	for(int i=15; i>=0; --i) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];	return f[x][0];}void update(int x) {	if(st[x]) { if(!(--cal[col[x]])) --ans; }	else { if(!(cal[col[x]]++)) ++ans; }	st[x]=!st[x];}bool check(int a, int b) { return cal[a] && cal[b] && a!=b; } //a!=bvoid pre() {	dfs((n+1)>>1);	for(int i=1; i<=m; ++i) {		q[i].x=getint(); q[i].y=getint(); q[i].a=getint(); q[i].b=getint(); q[i].id=i;		if(FF[q[i].x]>FF[q[i].y]) swap(q[i].x, q[i].y);		int lca=LCA(q[i].x, q[i].y);		q[i].y=FF[q[i].y];		if(lca==q[i].x) q[i].x=FF[q[i].x], q[i].lca=0;		else q[i].x=LL[q[i].x], q[i].lca=lca;	}	int nn=n<<1, sq=sqrt(nn+0.5);	for(int i=1; i<=nn; ++i) blo[i]=(i-1)/sq;	sort(q+1, q+1+m, cmp);}void work() {	int l=1, r=0, nl, nr;	for(int i=1; i<=m; ++i) {		nl=q[i].x; nr=q[i].y;		while(l
        
         nl) update(pos[--l]);		while(r
         
          nr) update(pos[r--]);		if(q[i].lca) update(q[i].lca);		Ans[q[i].id]=ans-check(q[i].a, q[i].b);		if(q[i].lca) update(q[i].lca);	}	for(int i=1; i<=m; ++i) printf("%d\n", Ans[i]);}int main() {	n=getint(); m=getint();	for(int i=1; i<=n; ++i) col[i]=getint();	for(int i=1; i<=n; ++i) {		int x, y; x=getint(); y=getint();		if(!x || !y) continue;		add(x, y);	}	pre();	work();	return 0;}
         
        
       
      
     

　　

无脑dfs序/分块树 树上分块= =

#include 
     
      using namespace std;const int N=50005, M=100005;int ihead[N], cnt, id[N], blo[N], f[N][16], dep[N], cal[N], col[N], st[N], n, m, Ans[M], ans, ID, n_blo, n_bl, sta[N], top;struct E { int next, to; }e[N<<1];struct Q { int x, y, a, b, id; }q[M];bool cmp(const Q &a, const Q &b) { return blo[a.x]==blo[b.x]?id[a.y]
      
       
        =n_blo) { ++n_bl; while(top!=last) blo[sta[top--]]=n_bl; }	}	sta[++top]=x;}int LCA(int x, int y) {	if(dep[x]
        
         =0; --i) if((d>>i)&1) x=f[x][i]; if(x==y) return x;	for(int i=15; i>=0; --i) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];	return f[x][0];}void update(int x) {	if(st[x]) { if(!(--cal[col[x]])) --ans; }	else { if(!cal[col[x]]) ++ans; ++cal[col[x]]; }	st[x]=!st[x];}void move(int x, int y) {	while(x!=y)		if(dep[x]>dep[y]) update(x), x=f[x][0];		else update(y), y=f[y][0];}bool check(int a, int b) { return cal[a] && cal[b] && a!=b; } //a!=bvoid pre() {	n_blo=sqrt(n+0.5);	dfs(1);	while(top) blo[sta[top--]]=n_bl;	for(int i=1; i<=m; ++i) { scanf("%d%d%d%d", &q[i].x, &q[i].y, &q[i].a, &q[i].b), q[i].id=i; if(id[q[i].x]>id[q[i].y]) swap(q[i].x, q[i].y); }	sort(q+1, q+1+m, cmp);	q[0].x=q[0].y=1;}void work() {	for(int i=1; i<=m; ++i) {		move(q[i-1].x, q[i].x); move(q[i-1].y, q[i].y);		int lca=LCA(q[i].x, q[i].y);		update(lca);		Ans[q[i].id]=ans;		if(check(q[i].a, q[i].b)) --Ans[q[i].id];		update(lca);	}	for(int i=1; i<=m; ++i) printf("%d\n", Ans[i]);}int main() {	scanf("%d%d", &n, &m); 	for(int i=1; i<=n; ++i) scanf("%d", &col[i]);	for(int i=1; i<=n; ++i) {		int x, y; scanf("%d%d", &x, &y);		if(!x || !y) continue;		add(x, y);	}	pre();	work();	return 0;}
        
       
      
     

 

upd：第二种写法：dfs序直接在序列中莫队= =

将树上的点转化为括号序列：每一个点的括号中包含了所有子树的节点：

可以得到：

（FF表示第一个括号的位置，LL表示第二个括号的位置）

当lca(x, y)!=x && !=y时且FF[x]<FF[y]时

• 区间[LL[x], FF[y]]出现奇数个数的节点就是x到y路径上的节点（但不包括lca）：

1. 1. 5由于LL[x]>FF[祖先]，所以[LL[x], FF[y]]中必有lca到x路径上的节点。而在这个区间内，lca的其它的非y的子树都会成偶数（FF[a]>FF[x] && LL[a]<FF[y] 或者 LL[a]<FF[x] 或者 FF[a]>FF[y]）。
   2. 而这个区间由于只是到FF[y]，因此FF[y]的祖先都是奇数次（因为y还没遍历完），所以区间内必有lca到y的路径上的节点（其中路径上的子树由于上边的理由同理），因此最终还剩下个lca，特判一下即可。

当lca(x, y)==x && FF[x]<FF[y]，区间[FF[x], FF[y]]表示出现奇数个数的节点就是x到y路径上的节点。和上面差不多的道理= =

所以搞搞就行辣= =速度超快= =

 

第一种写法：

树上分块= =

首先一开始就强行yy到了dfs序然后分块，后来不知什么鬼我自己不相信这样做能过这题（因为我一开始理解错啦= =假如固定了l，那么r走过的节点数是均摊O(n)的啊= =最多为2n次（进来又出去））

发现题解就是我一开始想的那样= =

可是我忽略了一个问题有木有！在更新lca的时候可能会出问题！自己画图可以得知！反正如果特判的话很难写的样子？

听说vfk神犇有题解我就去膜拜了下= =跪烂

首先设$S(u, v)$表示$u$到$v$路径上的节点集合。令$+$操作表示元素的模2加（即出现次数的模2加法，即异或= =，就是出现两次的就去掉）

容易得到$S(u, v) = S(root, u) + S(root, v) + lca(u, v)$

lca就是最麻烦的，vfk给出了一种巧妙的解法：

设$T(u, v) = S(root, u) + S(root, v)$

则设$u'$表示$u$要到达的目的地：

$$T(u, v) + T(u', v) = S(u, root) + S(u', root) + S(v, root) + S(v, root)$$

即

$$T(u', v) = T(u, u') + T(u, v)$$

那么我们要从$T(u, v)$转移到$T(u', v)$只需要走一次$T(u, u')$上的点就行辣！（注意踢掉lca）

而不选lca可以直接用向上爬的方法做= =很简单哒= =

然后计数颜色就开个计数器就行辣= =

然后就没辣= =