题目链接：
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1811
题目大意：
一棵树，N(2<=N<=105)个节点，每个节点有一种颜色Ci(Ci<=N)，问把每一条边删掉后，剩下的两个联通块中颜色的交集的大小(就是两边都含有的颜色种数)。
题目思路：
【树状数组】
我的数据结构造诣不深，这题写了暴力求每个点的颜色数T了。看了别人的题解写了超级久WA了好多才过。
首先可以知道，如果已知每个节点的子树中含有的颜色种数C和只出现在这棵子树的颜色种数D，那么这个节点和它的父亲节点中间的那条边被删去后的答案就是C-D。
所以问题变为求以每个节点为根的子树中的C和D值。然后我想到这里就不知道要怎么写了。看了大神的题解才有一点思路。（不过我感觉大神的题解好像有点问题？？）
首先转化成dfs序，按照遍历这棵树的顺序求出每个节点的新的从小到大的标号q[u].b(父亲标号先前于儿子),同时记下原先对应的节点标号q[u].id
预处理出对于颜色ci，记pre[ci]为ci上次出现的颜色位置,L[ci],R[ci]为ci出现的最左最右端。然后按照新的dfs序标号从小到大做
对于节点i，将pre[ci]到i之间的所有点ans+1(因为答案是一条条树链统计的，不会计算到兄弟节点，实际影响的只有这个节点以上的父亲节点，所以答案不会出错，本质上相当于把L[ci]到R[ci]所有的点都ans+1，但是只有有这种颜色的节点到根的树链上的点会加上答案，这样其实是没错的)
如果到了颜色的最右端，把这种颜色最左端左边的答案删掉（因为一开始pre默认是0，会把1~L[ci]中的答案+1，需要扣除，也可以一开始就从L[ci]开始加）
到达叶子结点后统计这条树链的答案。以上的ans可以用树状数组统计。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-10)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#pragma comment(linker,"/STACK:102400000,102400000")
#define N 100004
#define M 200004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
double anss;
LL aans;
int last[N],fa[N],c[N],pre[N],l[N],r[N],f[N],g[N],e[N];
struct edge
{
int from,next,to;
}a[M];
struct xu
{
int b,id;
}q[N];
void add(int x,int y)
{
a[++lll].to=y;
a[lll].from=x;
a[lll].next=last[x];
last[x]=lll;
}
bool cmp(xu aa,xu bb)
{
return aa.b<bb.b;
}
void dfs(int u,int father)
{
int i,v;
q[u].b=++cas,q[u].id=u;//b为新的按照dfs顺序的标号，id为原先标号
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
if(v==father)continue;
dfs(v,u);
e[q[v].b]=(i+)>>;//把新节点标号和原先的边的标号对应起来
fa[q[v].b]=q[u].b;//统计新节点标号的父亲
}
}
inline void modify(int x,int y)
{
int i;
for(i=x;i<=n;i+=lowbit(i))f[i]+=y;
}
inline int getsum(int x)
{
int i,sum=;
for(i=x;i;i-=lowbit(i))sum+=f[i];
return sum;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z;
// init();
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
lll=cas=;mem(last,);mem(l,);mem(r,);mem(pre,);mem(f,);
for(i=;i<=n;i++)scanf("%d",c+i);
for(i=;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(,);
sort(q+,q++n,cmp);
for(i=,j=q[i].id;i<=n;i++,j=q[i].id)
if(!l[c[j]])l[c[j]]=i;//统计每种颜色出现的最左端
for(i=n,j=q[i].id;i;i--,j=q[i].id)
if(!r[c[j]])r[c[j]]=i;//统计每种颜色出现的最右端
for(i=;i<=n;i++)
{
j=q[i].id;
modify(pre[c[j]]+,),modify(i+,-);//把上次这个颜色出现的位置到i之间的节点答案+1
pre[c[j]]=i;//pre记录的是这个颜色上一次出现的位置
if(i==r[c[j]])modify(,-),modify(l[c[j]]+,);//如果这种颜色出现最右端在这个点，那么把最左端左边的所有节点答案-1，因为颜色最左端的答案不能统计在内
if(a[last[j]].to==q[fa[i]].id)//如果当前结点是叶子结点
for(k=i;k!=;k=fa[k])g[e[k]]=getsum(k);//统计从根到这个叶子结点的树链的答案
}
for(i=;i<n;i++)
printf("%d\n",g[i]);
}
return ;
}
/*
// //
*/