题目描述

难度分:$2300$

输入$n(2 \leq n \leq 2 \times 10^5)$和$n-1$个数$p_2,p_3,…,p_n$，表示一棵$n$个节点的无根树，节点编号从$1$开始，$i$与$p_i(1 \leq p_i \leq i-1)$相连。

定义$a[x]$表示以$x$为根时的合法标记方案数，模$10^9+7$。其中【合法标记】定义为：对树的某些边做标记，使得$x$到任意点的简单路径上，至多有一条边是被标记的。

输出$a[1],a[2],…,a[n]$。

输入样例$1$

3
1 1

输出样例$1$

4 3 3

输入样例$2$

5
1 2 3 4

输出样例$2$

5 8 9 8 5

算法

换根DP

先来计算$a[1]$，此时$1$为树根。

状态定义

定义$f[i]$表示子树$i$的合法标记方案数。对于$i$的儿子$j$，考虑$i-j$这条边是否标记：

• 标记：那么子树$j$的所有边都不能标记，方案数为$1$。
• 不标记：那么方案数就是$f[j]$。

$i$的每个儿子互相独立，所以根据乘法原理有状态转移

$f[i]=(f[j_1]+1) \times (f[j_2]+1) \times … \times (f[j_m]+1)$

其中$j_1,j_2,…,j_m$是$i$的儿子。

状态转移

然后来计算其余$a[i]$。考虑把根从$i$换到$j$：
对于$j$来说，方案数需要在$f[j]$的基础上，再乘上【父亲$i$】这棵子树的方案数，即$\frac{a[i]}{f[j]+1}$。
所以$a[j] = f[j] \times (\frac{a[i]}{f[j]+1} + 1)$

本题的一个易错点是，$f[j]+1$可能等于$mod=10^9+7$，取模会变成$0$，但是$0$没有逆元。处理方式有很多，我的做法是用前后缀积的组合来得到这个商。

复杂度分析

时间复杂度

树的边数和点数是一个级别的，而整个算法做了两遍$DFS$，因此时间复杂度为$O(n)$。

空间复杂度

树的邻接表空间复杂度为$O(n)$。初始DP数组$f$空间复杂度为$O(n)$。第二次$DFS$的过程中使用的前后缀积数组，空间复杂度大概也是整棵树的节点个数，为$O(n)$。树形DP的递归深度在最差情况下也是$O(n)$，因此空间复杂度为$O(n)$。

综上，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 1e9 + 7;
int n, p[N], f[N], a[N];
vector<int> graph[N], pre[N], suf[N];

void dfs1(int u, int fa) {
    f[u] = 1;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        f[u] = (LL)f[u] * (f[v] + 1) % MOD;
    }
}

void dfs2(int u, int fa) {
    int sz = graph[u].size();
    a[u] = f[u];
    for(int v: graph[u]){
        pre[u].push_back((f[v] + 1) % MOD);
        suf[u].push_back((f[v] + 1) % MOD);
    }
    for(int i = 1; i < sz; i++) {
        pre[u][i] = (LL)pre[u][i - 1] * pre[u][i] % MOD;
    }
    for(int i = sz - 2; i >= 0; i--) {
        suf[u][i] = (LL)suf[u][i + 1] * suf[u][i] % MOD;
    }
    for(int j = 0; j < sz; j++) {
        int v = graph[u][j];
        if(v == fa) continue;
        f[u] = (LL)(j > 0? pre[u][j - 1]: 1) * (j < sz - 1? suf[u][j + 1]: 1) % MOD;
        f[v] = (LL)f[v] * ((f[u] + 1) % MOD) % MOD;
        dfs2(v, u);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
        pre[i].clear();
        suf[i].clear();
    }
    for(int i = 2; i <= n; i++) {
        scanf("%d", &p[i]);
        graph[i].push_back(p[i]);
        graph[p[i]].push_back(i);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}