题意：

有一棵树包含N个节点，节点编号从1到N。节点总共有K种颜色，颜色编号从1到K。第i个节点的颜色为$A_i$。

$F_i$表示恰好包含i种颜色的路径数量。请计算：

$\left(\sum_{i=1}^k(F_i*131^i)\right)\ mod\ (10^9+7)$。

其中$1≤N≤50000$，$1≤K≤10$。

思路：

做的时候完全无从下手QAQ

突破点是在这个k，由范围看出可以用状压，压什么呢？压路径中颜色的使用情况。

比如k=5，dp[10010]表示的就是路径中有第一种和第四种颜色的路径数（事实上表示的是只有第一种+只有第四种+恰好有第一种和第四种）。

那么知道了某一种状态，要如何求出路径数呢？

dfs一下，把有这些颜色的并连通的视为一个连通块，在连通块内部路径数为cnt*(cnt-1)/2（每两个不同的点之间一条路径），这里注意一个点也算一条路径，这个就放在最后进行计算。

所以枚举颜色的使用情况，进行dfs就可以算出dp。

之前括号里也说了这样子出来的dp表示的不是恰好有这些颜色的，而是有不超过这些颜色的路径总数。

所以这里就要用到容斥了。

ans表示的是恰好有这些颜色的路径数。

ans[111]

=dp[111]-ans[110]-ans[101]-ans[011]-ans[001]-ans[010]-ans[100]

=dp[111]-(dp[110]-dp[100]-dp[010])-(dp[101]-dp[100]-dp[001])-(dp[011]-dp[010]-dp[001])-dp[001]-dp[010]-dp[100]

=dp[111]-dp[110]-dp[101]-dp[011]+dp[001]+dp[010]+dp[100]

由此可以看出，如果子集和它相差的颜色是奇数的话，就减，如果相差的是偶数的话，就加。

最后再把一个结点的情况加上就可以了。

复杂度是$O(2^k*n)$。

代码：

#define MOD 1000000007
typedef long long ll;
ll f[15];
int col[50010];
ll dp[1500];
vector<int>v[50010];
bool rcol[15];
bool vis[50010];
ll num[50010];
ll cnt=0;
ll ans[1500];
void dfs(int id)
{
    vis[id]=true;
    cnt++;
    for(int i=0;i<v[id].size();i++)
    {
        int temp=v[id][i];
        if(!vis[temp]&&rcol[col[temp]])
            dfs(temp);
    }
}
int main()
{
    int n,k,x,y;
    scanf("%d%d",&n,&k);
    f[0]=1;
    for(int i=1;i<=k;i++)
        f[i]=(f[i-1]*131)%MOD;
    for(int i=1;i<=n;i++)
        scanf("%d",&col[i]);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<(1<<k);i++)
    {
        memset(vis,0,sizeof(vis));
        memset(rcol,0,sizeof(rcol));
        cnt=0;
        for(int j=1;j<=k;j++)
        {
            if(1<<(j-1)&i)
            {
                rcol[j]=true;
                cnt++;
            }
        }
        num[i]=cnt;
        /*for(int i=1;i<=k;i++)
            printf("%d ",rcol[i]);
        printf("\n");*/
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&rcol[col[j]])
            {
                cnt=0;
                dfs(j);
                //printf("(%d %d %lld)\n",i,j,cnt);
                dp[i]+=(cnt*(cnt-1)/2)%MOD;
            }
        }
    }
    /*for(int i=1;i<(1<<k);i++)
        printf("%lld ",num[i]);
    printf("\n");
    for(int i=1;i<(1<<k);i++)
        printf("%lld ",dp[i]);
    printf("\n");*/
    for(int i=1;i<(1<<k);i++)
    {
        ans[i]=dp[i];
        for(int j=1;j<(1<<k);j++)//j是i的子集
        {
            if((i|j)==i&&i!=j)
            {
                //printf("%d %d\n",i,j);
                if((num[i]-num[j])%2==1)ans[i]=(ans[i]-dp[j]+MOD)%MOD;
                else ans[i]=(ans[i]+dp[j])%MOD;
            }
        }
    }
    /*for(int i=1;i<(1<<k);i++)
        printf("%lld ",ans[i]);
    printf("\n");*/
    ll aans=0;
    for(int i=1;i<(1<<k);i++)
        aans=(aans+(ans[i]*f[num[i]])%MOD)%MOD;
    aans=(aans+n*f[1])%MOD;
    printf("%lld\n",aans);
    return 0;
}

总结：

看到范围小的，可以想到状压也可以想到全排列。