链接：/acm/contest/904/E
来源：牛客网
题目描述
DongDong是个喜欢数颜色的女孩子，她已经熟练地掌握了在序列上数颜色的操作，现在她开始学习如何在树上数颜色，现在给定一个n个点,n-1条边的树形图（视1号店为根），每个点有一个颜色，每次询问以x为根的子树中有多少种不同的颜色，DongDong轻松地解决了这个问题，但她想考考会编程的你。
输入描述:
第一行两个整数n,m第二行n个整数，表示每个点的颜色接下来n-1行每行u,v,表示存在一条从u到v的双向边（保证最终图形是树形图）2<=n<=100000,1<=m,color<=n，
输出描述:
共m行：每行输出相应询问的答案
示例1
输入
4 31 1 2 31 22 31 4124
输出
321
题解：
刚开始用bitset去维护每个点出现的颜色的集合（有哪个颜色哪个二进制位就是1），dfs的时候进行或运算维护就可以了，然后超内存了。/p/NwfHgtJZYJ/
然后我看见讨论区有人用set过了，每个节点用一个set去维护，我算了一下，这个复杂度过不了，比如有1e5个点，每个点颜色都不一样，树是一个链状的，需要进行 1+2+3+...n 次插入操作，每次插入的复杂度是logn,总时间复杂度O(n*n*logn).1e5的数据过不了。题目的数据太水了。
我用树状数组做的。复杂度O(nlogn).
先dfs求出这棵树的dfs序。然后问题就转化成求区间不同数字的个数。求区间不同数字的个数是一个很经典的树状数组离线做法，维护每个颜色最后出现的位置。
以前做过一个求区间不同数字的和，链接/weixin_42757232/article/details/90691366
代码：
#include<bits/stdc++.h>using namespace std;const int maxn=2e5+5;int bit[maxn];int color[maxn];int a[maxn],tot;int head[maxn/2],nex[maxn],to[maxn],cnt;int ans[maxn];int pos[maxn];int n,m;struct node{int l,r,id;}q[maxn];bool cmp(node a,node b){return a.r<b.r;}void addEdge(int i,int j){to[++cnt]=j;nex[cnt]=head[i];head[i]=cnt;}void dfs(int x,int f){a[++tot]=x;for(int i=head[x];~i;i=nex[i]){int j=to[i];if(j==f) continue;dfs(j,x);}a[++tot]=x;}void add(int x,int v){while(x<=2*n){bit[x]+=v;x+=x&-x;}}int sum(int x){int ans=0;while(x){ans+=bit[x];x-=x&-x;}return ans;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",color+i);memset(head,-1,sizeof head);for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);addEdge(a,b);addEdge(b,a);}dfs(1,-1);for(int i=1;i<=2*n;i++){int x=a[i];if(q[x].l==0){q[x].l=i;q[x].id=x;}else{q[x].r=i;}}sort(q+1,q+n+1,cmp);for(int i=1,j=1;i<=n;i++){while(j<=q[i].r){if(pos[color[a[j]]]){add(pos[color[a[j]]],-1); //已经出现过，在上一次出现的位置-1}pos[color[a[j]]]=j;add(j,1);j++;}ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);}while(m--){int x;scanf("%d",&x);printf("%d\n",ans[x]);}return 0;}
