状压dp、容斥

首先我们要知道树的一个重要的特性：
对于树来说，他的路径总和为: $\frac{n*(n-1)}{2}$

刚开始我想换根dp。。。。
还以为自己想到了一个新的方法。。。。
打算先以1为根处理以每个节点为起点，到其子树中找路径能找到的路径和
然后再通过找子结点和父节点的关系从而换根

但是，这里的路径，只是通过找子结点和父节点的关系我们是无法换根的！！！
与整个路径的状态有关！！
那么就是状压了！

我们可以枚举我们要选的颜色一共也不过 $1<<k$ 种
然后我们统计：路径中的颜色种类包含在这个状态里的数量

注意！我们这里不是统计正好颜色数就是这么多的路径数！
比如我们枚举的颜色为 1 2 3
那么只包含颜色 1 2 的路径也在我们的统计范围！！

为什么要这样呢？？
其实我们是可以注意到的要找准确的一条路径是十分困难的！！

转化问题后就简单了！
我们可以将属于这个颜色的节点先筛选出来
然后看他们形成几个树！！！
之后通过开头的那个树的性质，我们直接得到了答案！！！

最后，我们再利用容斥原理对最终答案景行求解！

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll base = 131;
const int max_n = 5e4+100;
struct edge{
    int to,next;
}E[max_n<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}
int N,K;
int color[max_n];
ll f[1<<11];
bool vis[max_n];

int dfs(int u,int ste){
    vis[u]=1;
    if (!(color[u]&ste))return 0;
    int ans=1;
    for (int i=head[u];i;i=E[i].next){
        int v = E[i].to;
        if (vis[v])continue;
        ans+=dfs(v,ste);
    }return ans;
}

ll fac[15];
int main(){
    ios::sync_with_stdio(0);
    cin>>N>>K;fac[0]=1;
    for (int i=1;i<=K;++i)fac[i]=fac[i-1]*base%mod;
    for (int i=1,j;i<=N;++i){
        cin>>j;color[i]|=(1<<(j-1));
    }
    for (int i=1,u,v;i<N;++i){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for (int i=1;i<(1<<K);++i){
        fill(vis,vis+N+10,0);
        for (int u=1;u<=N;++u){
            if (!vis[u]){
                ll tot = dfs(u,i);
                f[i]=(f[i]+tot+tot*(tot-1)/2%mod)%mod;
            }
        }
    }
    ll ans = 0;
    for (int i=1;i<(1<<K);++i){
        for (int j=i&(i-1);j;j=(j-1)&i)f[i]-=f[j];
        ans = (ans+f[i]*fac[__builtin_popcount(i)]%mod)%mod;
    }cout<<ans<<endl;
}

这里学到了一个枚举技巧。

for (int j=i&(i-1);j;j=(j-1)&i)

枚举位数为1的个数小于i的状态！

多彩的树

状压dp、容斥