Description
神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个1到N之间的正整数来表示一种颜色。树上一共有N个苹果。每个苹果都被编了号码，号码为一个1到N之间的正整数。我们用0代表树根。只会有一个苹果直接连到树根。
有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为N的苹果出发，由树枝走到编号为N的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果u和苹果v的颜色）？不过神犇注意到，有些来膜拜的人患有色盲症。具体地说，一个人可能会认为颜色a就是颜色b，那么他们在数苹果的颜色时，如果既出现了颜色a的苹果，又出现了颜色b的苹果，这个人只会算入颜色b，而不会把颜色a算进来。
神犇是一个好人，他不会强人所难，也就会接受由于色盲症导致的答案错误（当然答案在色盲环境下也必须是正确的）。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟，但是他想考验一下你。你能替神犇完成这项任务吗？
N<=50000,M<=100000
Solution
- 第一道莫队，也是树上莫队。
- 模板题，没有什么可说的。
- 注意记录一个节点被遍历了几遍（0/1），分奇数次和偶数次计算贡献。
- 奇偶数优化很关键，快了一倍。。。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define maxp 20
#define maxm 100005
using namespace std;
int n,m,i,j,k,x,y,rt,c[maxn];
int em,e[maxm],ls[maxn],nx[maxm];
int dep[maxn],fa[maxn][maxp];
int fir[maxn],las[maxn],tot,d[maxn],tp[maxn];
int K,t[maxn],ans,qans[maxm];
struct que{
int l,r,a,b,li,i,lca;
} q[maxm];
int cmp(que a,que b){return a.li<b.li||a.li==b.li&&((a.li&1)?(a.r<b.r):(a.r>b.r));}
void read(int &x){
char ch=getchar(); x=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em;
}
void DFS(int x,int p){
d[++tot]=x,tp[x]=1,fir[x]=tot;
fa[x][0]=p,dep[x]=dep[p]+1;
for(int i=1;i<maxp;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=ls[x];i;i=nx[i]) if (e[i]!=p)
DFS(e[i],x);
d[++tot]=x,tp[x]=-1,las[x]=tot;
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for(int i=maxp-1;i>=0;i--) if (dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if (x==y) return x;
for(int i=maxp-1;i>=0;i--) if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void change(int i){
if (tp[d[i]]>0) ans+=!t[c[d[i]]]++; else
ans-=!--t[c[d[i]]];
tp[d[i]]=-tp[d[i]];
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++) read(c[i]);
for(i=1;i<=n;i++) read(x),read(y),insert(x,y);
rt=e[ls[0]];
DFS(rt,0);
K=sqrt(tot);
for(i=1;i<=m;i++){
read(x),read(y),read(q[i].a),read(q[i].b);
if (fir[x]>fir[y]) swap(x,y);
q[i].lca=lca(x,y),q[i].i=i;
if (q[i].lca==x) q[i].l=fir[x],q[i].r=fir[y];
else q[i].l=las[x],q[i].r=fir[y];
q[i].li=(q[i].l-1)/K+1;
}
sort(q+1,q+1+m,cmp);
for(i=1;i<=n;i++) tp[i]=1;
i=1,j=0;
for(k=1;k<=m;k++){
while (j<q[k].r) change(++j);
while (j>q[k].r) change(j--);
while (i<q[k].l) change(i++);
while (i>q[k].l) change(--i);
qans[q[k].i]=ans;
if (!t[c[q[k].lca]]) qans[q[k].i]++;
if (q[k].a!=q[k].b){
t[c[q[k].lca]]++;
if (t[q[k].a]&&t[q[k].b]) qans[q[k].i]--;
t[c[q[k].lca]]--;
}
}
for(i=1;i<=m;i++) printf("%d
",qans[i]);
}