题解

　　因为一个sb错误调了一个晚上……鬼晓得我为什么$solve(rt)$会写成$solve(v)$啊！！！一个$O(logn)$被我硬生生写成$O(n)$了竟然还能过$5$个点……话说还一直以为只有动态点分会很难没想到一般点分都这么可啪……%%%

　　我们考虑一下，对于一棵树，我们要处理的是子树对根的答案的贡献，以及经过根的路径的贡献（也就是$LCA$为根的点对的答案）。

　　对于树中的一个点$i$，如果$i$的颜色是在$i$到根的路径上第一次出现，那么所有与$i$的$LCA$为根的点，都能与$i$的子树形成点对，且$i$的颜色会对那些点产生产生贡献$size[i]$（先不考虑其他子树中是否有相同颜色）。

　　那么我们考虑$dfs$一遍整棵树，并记录，所有颜色产生的贡献$col[i]$以及贡献总和$sum$。然后$dfs$子树，并把其中的所有颜色的贡献给减掉。然后考虑子树中的一个点，设$x$为到根上的所有点的贡献总和，$num$表示根到节点上的颜色个数，$y=size[root]-size[该子树]$，那么$ans[j]+=sum-x+num*size[y]$

　　然后最后记得加上对根节点的答案的贡献$ans[root]+=sum-col[根的颜色]+size[root]$

　　不得不说思路真的挺妙的

1 //minamoto  2 #include
     
        3 #include
      
         4 #include
       
          5 #define ll long long  6 using namespace std;  7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)  8 char buf[1<<21],*p1=buf,*p2=buf;  9 template
        
         inline bool cmax(T&a,const T&b){
   return a
         
          1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 24     while(z[++Z]=x%10+48,x/=10); 25     while(sr[++C]=z[Z],--Z);sr[++C]='\n'; 26 } 27 const int N=200005; 28 int head[N],Next[N<<1],ver[N<<1],c[N],son[N],sz[N],size,cnt[N]; 29 ll col[N],ans[N],much,sum,num; 30 int tot,n,rt;bool vis[N]; 31 inline void add(int u,int v){ 32     ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 33     ver[++tot]=u,Next[tot]=head[v],head[v]=tot; 34 } 35 void findrt(int u,int fa){ 36     sz[u]=1,son[u]=0; 37     for(int i=head[u];i;i=Next[i]){ 38         int v=ver[i]; 39         if(!vis[v]&&v!=fa){ 40             findrt(v,u); 41             sz[u]+=sz[v]; 42             cmax(son[u],sz[v]); 43         } 44     } 45     cmax(son[u],size-sz[u]); 46     if(son[u]