苹果树（树上莫队）

• Description
  　　神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。
  　　有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为u的苹果出发，由树枝走到编号为v的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果u和苹果v的颜色）？不过神犇注意到，有些来膜拜的人患有色盲症。具体地说，一个人可能会认为颜色a就是颜色b，那么他们在数苹果的颜色时，如果既出现了颜色a的苹果，又出现了颜色b的苹果，这个人只会算入颜色b，而不会把颜色a算进来。
  　　神犇是一个好人，他不会强人所难，也就会接受由于色盲症导致的答案错误（当然答案在色盲环境下也必须是正确的）。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟，但是他想考验一下你。你能替神犇完成这项任务吗？
• Input
  　　输入第一行为两个整数n和m，分别代表树上苹果的个数和前来膜拜的人数。
  　　接下来的一行包含n个数，第i个数代表编号为i的苹果的颜色Coli。
  　　接下来有n行，每行包含两个数x和y，代表有一根树枝连接了苹果x和y（或者根和一个苹果）。
  　　接下来有m行，每行包含四个整数u、v、a和b，代表这个人要数苹果u到苹果v的颜色种数，同时这个人认为颜色a就是颜色b。如果a=b=0，则代表这个人没有患色盲症。
• Output
  　　输出一共m行，每行仅包含一个整数，代表这个人应该数出的颜色种数。
• Sample Input
  5 3
  1 1 3 3 2
  0 1
  1 2
  1 3
  2 4
  3 5
  1 4 0 0
  1 4 1 3
  1 4 1 2
• Sample Output
  2
  1
  2
• Hint
  0<=x,y,a,b<=N
  N<=50000
  1<=U,V,Coli<=N
  M<=100000

树上莫队：（大佬跳过）
我们需要处理每个前来膜拜的人，一个一个太浪费时间了，于是我们就考虑如何让前面的人计算好的为后面的计算服务，于是我们每次就只需要操作两个问题的相异就行了：
但有些数据非常坑，修改很远，这就需要树上分块来预处理了
思路：
有了树上莫队，这道题就很水了，基本可以算板子题，需要注意的是特判色盲就行了

代码如下：

#include<bits/stdc++.h>
using namespace std;
int st[50005],B;
int color[50005];
int f[50005][20];
int b[50005],n,m,asdf;
int h[50005],q[50005];
int num[50005],cnt,ans;
int d[50005],vis[50005];
struct node {int to,next;
} e[100005];
struct query {int x,y,a,b,id;
} a[100005];
bool cmp(query x,query y) {if(b[x.x]==b[y.x])return b[x.y]<b[y.y];return b[x.x]<b[y.x];
}
void Addedge(int x,int y) {e[++cnt]=(node) {y,h[x]};h[x]=cnt;
}
void Dfs(int x,int prt) {d[x]=d[prt]+1;int i,y,op=st[0];f[x][0]=prt;for(i=1; i<=16; ++i) {if(d[x]<(1<<i))break;f[x][i]=f[f[x][i-1]][i-1];}for(i=h[x]; i; i=e[i].next) {int y=e[i].to;if(y==prt)continue;Dfs(y,x);if(st[0]-op>=B) {++asdf;while(st[0]-op)b[st[st[0]--]]=asdf;}}st[++st[0]]=x;
}
int Lca(int x,int y) {int i,k;if(d[x]<d[y])swap(x,y);k=int(log(d[x])/log(2));for(i=k; i>=0; i--)if(d[x]-(1<<i)>=d[y])x=f[x][i];if(x==y)return x;for(i=k; i>=0; i--)if(f[x][i]!=-1&&f[x][i]!=f[y][i]) {x=f[x][i];y=f[y][i];}return f[x][0];
}
void Reserve(int x) {if(!vis[x]) {if(!num[color[x]])++ans;++num[color[x]];} else {--num[color[x]];if(!num[color[x]])--ans;}vis[x]^=1;
}
void Solve(int x,int y) {while(x!=y) {if(d[x]>d[y]) {Reserve(x);x=f[x][0];} else {Reserve(y);y=f[y][0];}}
}
int main() {scanf("%d%d",&n,&m);B=pow(n,0.5);for(int i=1; i<=n; ++i)scanf("%d",&color[i]);for(int i=1; i<=n; ++i) {int x,y;scanf("%d%d",&x,&y);Addedge(x,y);Addedge(y,x);}Dfs(0,0);while(st[0])b[st[st[0]--]]=asdf;for(int i=1; i<=m; ++i)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b),a[i].id=i;sort(a+1,a+m+1,cmp);Solve(a[1].x,a[1].y);int t=Lca(a[1].x,a[1].y);Reserve(t);q[a[1].id]=ans;if(num[a[1].a]&&num[a[1].b]&&a[1].a!=a[1].b)--q[a[1].id];Reserve(t);for(int i=2; i<=m; ++i) {Solve(a[i-1].x,a[i].x);Solve(a[i-1].y,a[i].y);int t=Lca(a[i].x,a[i].y);Reserve(t);q[a[i].id]=ans;if(num[a[i].a]&&num[a[i].b]&&a[i].a!=a[i].b)--q[a[i].id];Reserve(t);}for(int i=1; i<=m; ++i)printf("%d\n",q[i]);return 0;
}