51Nod-1868-彩色树

ACM模版

描述

题解

树型DP，先上官方题解：

官方题解说的十分清楚，和我的代码思路也恰好吻合，大体上是针对每种颜色求出不包括该种颜色的路径的点对儿数目之和。最后用 col_num∗cal(n)col_num * cal(n) 减去前边求的和即为树上任意不同两点之间路径包含的颜色种类之和，然后再乘以 (n−1)!(n - 1)! 即可。

总得来说就是一个逆向思维的树型DP，要直接求任意不同两点之间路径包含颜色种类之和并不好求，我们反过来很容易便可以求出来不包含颜色的总和，用全集减去不包含的即为我们要求的，其他也就没啥不好理解的了。

代码

代码语言：javascript复制

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN = 1e5   5;
const int MOD = 1e9   7;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10   (c - '0'), c = getchar();
    }
}

int tot = 0;
int hed[MAXN];
int nxt[MAXN << 1];
int val[MAXN << 1];

void addEdge(int x, int y)
{
    val[  tot] = y;
    nxt[tot] = hed[x];
    hed[x] = tot;
}

int cal(int x)
{
    return (ll)(x - 1) * x % MOD;
}

int n;
int col_num, ans;
int sz[MAXN];
int col[MAXN];
int sum[MAXN];
bool vis[MAXN];

void dfs(int rt, int pre)
{
    sz[rt] = 1;
    int now, tmp;
    for (int i = hed[rt]; i; i = nxt[i])
    {
        if (val[i] != pre)
        {
            now = sum[col[rt]];

            dfs(val[i], rt);

            tmp = sz[val[i]] - (sum[col[rt]] - now);
            ans  = cal(tmp);
            ans %= MOD;
            sum[col[rt]]  = tmp;
            sz[rt]  = sz[val[i]];
        }
    }
    sum[col[rt]]  ;
}

int main()
{
    scan_d(n);
    for (int i = 1; i <= n; i  )
    {
        scan_d(col[i]);
        if (!vis[col[i]])
        {
            col_num  ;
            vis[col[i]] = 1;
        }
    }

    int x, y;
    for (int i = 1; i < n; i  )
    {
        scan_d(x);
        scan_d(y);
        addEdge(x, y);
        addEdge(y, x);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i  )
    {
        if (vis[i])
        {
            ans  = cal(n - sum[i]);
            ans %= MOD;
        }
    }
    ans = ((ll)col_num * cal(n) % MOD - ans   MOD) % MOD;
    for (int i = 1; i < n; i  )
    {
        ans = (ll)ans * i % MOD;
    }

    printf("%dn", ans);

    return 0;
}

0 人点赞