A、多彩的树

看到颜色最大只有10种，考虑枚举全部的颜色搭配，二进制枚举即可 $图片说明$
我们选取二进制位是1的表示该颜色本轮被选取。例如1011->第一种第二种第四种颜色被选取，第三种没被选中。
这样一重循环枚举颜色组合，再去遍历这种颜色组合下的全部节点，通过DFS跑出每个符合颜色要求的连通块节点数。
我们又知道在这个连通块里，可以去到的节点都是合法节点，既可看成是一个无向完全图，路径数为 $图片说明$ n为当前连通块节点数。
那么跑出这个颜色状态下全部的连通块节点数，把路径数全部累加，并且加上路径数为0的全部只选取一个节点的涂法，即可更新出每个颜色的答案。
这个地方需要注意，我们通过二进制枚举颜色，DFS跑连通块是通过一个或运算判断是否在这个枚举颜色中，那么举个例子1011的颜色1000重复计算了。
需要再计算最终答案的时候枚举一下前面重复的更少颜色的减掉。最后注意取余的减法就行了
图片说明

Code

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == &#39;-&#39;) w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 5e4 + 7; //节点数
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int head[N], tot = 0;//前向星变量
struct Node {
    int v, next;
} edge[N << 1];
int a[N], fac[N];
ll cnt;
bool vis[N];
int dp[1 << 11];

void add(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}

void dfs(int u, int fa, int s) { //dfs跑连通块
    if ((a[u] | s) != s || vis[u])    return;
    vis[u] = 1; ++cnt; //cnt返回连通块节点个数
    for (int i = head[u]; i; i = edge[i].next)
        if (edge[i].v != fa)    dfs(edge[i].v, u, s);
}

int main() {
    int n = read(), k = read();
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)    fac[i] = 1ll * fac[i - 1] * 131 % MOD;
    for (int i = 1; i <= n; ++i) {
        int x = read();
        a[i] = 1 << (x - 1); //每种颜色占二进制中一个1的位置
    }
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add(u, v);    add(v, u);
    }

    //二进制枚举全部可能颜色组合
    for (int i = 1; i < (1 << k); ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= n; ++j)
            if (!vis[j]) {
                cnt = 0;
                dfs(j, 0, i);
                dp[i] = (dp[i] + cnt + cnt * (cnt - 1) / 2) % MOD;
            }
    }
    int ans = 0;
    for (int i = 1; i < (1 << k); ++i) {
        for (int j = (i - 1) & i; j; j = (j - 1) & i)
            dp[i] -= dp[j]; //斥容
        ans = (ans + 1ll * fac[__builtin_popcount(i)] * dp[i] % MOD) % MOD;
    }
    printf("%d\n", (ans + MOD) % MOD);
    return 0;
}

牛客算法周周练5

A、多彩的树

Code