首先可以转化问题，变为对每种颜色分别考虑不含该颜色的简单路径条数。然后把不是当前颜色的点视为白色，是当前颜色的点视为黑色，显然路径数量是每个白色连通块大小的平方和，然后题目变为：黑白两色的树，单点翻转颜色，维护白色连通块大小平方和，然后根据Auuan大佬的题解，我用了LCT。就是对每个点维护子树、儿子大小平方和，在 link/cut 的时候更新答案。初始化所有点是白色，离线处理每个颜色即可。

这题放在2h比赛上，除了lxl其他人都写不出来（况且lxl还是本题出题人呢）

#include
      
       using namespace std;typedef long long ll;const int N=4e5+7;int n,m,c[N],f[N],fa[N],ch[N][2],sum[N],sz[N];ll ans,d[N],sz2[N];bool vis[N];vector
       
        vec[N][2],G[N];bool nroot(int x){
    return x==ch[fa[x]][0]||x==ch[fa[x]][1];}void pushup(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+sz[x]+1;}void rotate(int x){    int y=fa[x],z=fa[y],w=x==ch[y][1];    if(nroot(y))ch[z][y==ch[z][1]]=x;    fa[x]=z,ch[y][w]=ch[x][w^1],fa[ch[x][w^1]]=y,ch[x][w^1]=y,fa[y]=x;    pushup(y),pushup(x);}void splay(int x){    while(nroot(x))    {        int y=fa[x],z=fa[y];        if(nroot(y))        {            if((x==ch[y][1])^(y==ch[z][1]))rotate(x);            else rotate(y);        }        rotate(x);    }}void access(int x){    int y=0;    while(x)    {        splay(x);        sz[x]+=sum[ch[x][1]]-sum[y];        sz2[x]+=1ll*sum[ch[x][1]]*sum[ch[x][1]]-1ll*sum[y]*sum[y];        ch[x][1]=y;        pushup(x);        x=fa[y=x];    }}int findrt(int x){    access(x),splay(x);    while(ch[x][0])x=ch[x][0];    splay(x);    return x;}void link(int x){    int y=f[x],z;    splay(x);    ans-=sz2[x]+1ll*sum[ch[x][1]]*sum[ch[x][1]];    z=findrt(y);    access(x),splay(z);    ans-=1ll*sum[ch[z][1]]*sum[ch[z][1]];    fa[x]=y;    splay(y);    sz[y]+=sum[x],sz2[y]+=1ll*sum[x]*sum[x];    pushup(y),access(x),splay(z);    ans+=1ll*sum[ch[z][1]]*sum[ch[z][1]];}void cut(int x){    int y=f[x],z;    access(x);    ans+=sz2[x];    z=findrt(y);    access(x),splay(z);    ans-=1ll*sum[ch[z][1]]*sum[ch[z][1]];    splay(x);    ch[x][0]=fa[ch[x][0]]=0;    pushup(x),splay(z);    ans+=1ll*sum[ch[z][1]]*sum[ch[z][1]];}void dfs(int u){
     for(int i=0;i