【每日一题】4月7日 树

dp做法

时间复杂度。

在树中选择任意一个叶子结点作为起点，沿着边一个点接一个点的涂色。定义为前个点使用了种颜色的方案数，状态转移方程：

• 若第个点选用未使用的颜色，则。
• 若第个点选用已经使用过的颜色，则必须和的颜色相同，若和更前面的结点颜色相同则在路径中会经过不符合题意，则。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

int n, k;
int u, v;
LL dp[377][377];
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1);
            dp[i][j] %= mod;
        }
    }
    for(int j = 1; j <= k; j++) {
        dp[n][j] = (dp[n][j] + dp[n][j - 1]) % mod;
    }
    printf("%lld\n", dp[n][k]);
    return 0;
}

连通块做法

时间复杂度，下面代码中的逆元可以进一步优化。

问题转化为把一棵树分成多个连通块，每个连通块内的结点涂相同的颜色，不同的连通块颜色不同，有多少种方案。

• 若把个结点的树分成个连通块，则需要删除条边，有种方案。
• 种颜色需要选出种，有种方案。
• 种颜色涂个连通块，有种方案。
• 上面三个条件满足乘法原理，则对答案的贡献为，最后只需要枚举一下可以分成多少个连通块求和即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

int n, k;
int u, v;
LL fac[377], sum;
LL fast_pow(LL a, LL n) {
    LL ret = 1, temp = a % mod;
    while(n) {
        if(n & 1) ret = ret * temp % mod;
        temp = temp * temp % mod;
        n >>= 1;
    }
    return ret;
}
LL Comb(int n, int m) {
    return fac[n] * fast_pow(fac[m] * fac[n - m], mod - 2) % mod;
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
    fac[0] = fac[1] = 1;
    for(int i = 2; i < 377; i++) fac[i] = fac[i - 1] * i % mod;
    if(k > n) k = n;
    for(int i = 1; i <= k; i++) {
        sum = (sum + Comb(n - 1, i - 1) * Comb(k, i) % mod * fac[i]) % mod;
    }
    printf("%lld\n", sum);
    return 0;
}

dfs序

总感觉以前听学长提起过，自己最近好像用过，遂翻了翻笔记，原来打Codeforces Round #629 (Div. 3)的E题时用到了，笔记地址http://www.kindkidll.com/index.php/archives/120/。
下图是一颗树加了时间戳的遍历结果，dfs序的好处在于把树形结构转化成了线性结构。假设要进行操作把某棵子树的结点加上某个值，求某棵子树结点的和，转化成线性结构后问题就变成线段树的区间更新和区间查询了。