Subtree

所谓换根法，一种做法是在根移动到孩子节点的时候，计算新的DP的值，另外一种相关的做法，是对于每一个节点 $i$ ，计算两个DP的值，其中DP1是 $i$ 子树内的值，而DP2是 $i$ 子树外的值。本题用后面的构造方法来解比较自然：

$\texttt{dp}[s][0] = \prod_{u \in C_s} (\texttt{dp}[u][0]+1)$ ，这是 $s$ 子树内的方案数。
$\texttt{dp}[u][1] = dp[s][1] \cdot \prod_{v \in S_u} (\texttt{dp}[v][0]+1)$ ，这是 $u$ 子树外的方案数（ $v$ 是 $u$ 的兄弟）

这样的话，答案就是： $dp[s][0] \cdot dp[s][1]$

上面第二个式子中的 $u$ 的兄弟的值+1的乘积，可以用prefix/suffix product来算，这样每个节点访问常数前，最后的整体复杂度还是 $\mathcal{O}(n)$ 。

第一种换根思路不通：根据树形DP - 换根中的例题的做法，可以想到本题也有一个简单换根的想法:

\texttt{dp}[s] = \prod (\texttt{dp}[u]+1) \\ \texttt{dp}'[s] = \frac {\texttt{dp}[s]} {\texttt{dp}[u]+1} \\ \texttt{dp}'[u] = \texttt{dp}[u] \cdot (\texttt{dp}'[s]+1) \\

但这个写不出来，因为题目要求用取模运算，这里这个除法不好做。因为题中给的模 $M$ 不是质数，所以不能用费马小定理取反。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, M;
vector<int> adj[100005];
int dp[100005][2];
int ans[100005];
 
void dfs1(int s, int e) {
    dp[s][0] = 1;
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs1(u, s);
        dp[s][0] = ((ll)dp[s][0] * (dp[u][0]+1)) % M;
    }
}
 
void dfs2(int s, int e) {
    int pre = 1;
    vector<int> post(1, 1);
    for (int i = adj[s].size()-1; i >= 0; i--) { // calc postfix sum
        int u = adj[s][i];
        int v = u == e ? 1 : (dp[u][0] + 1);
        post.push_back(((ll)post.back() * v) % M);
    }
    for (int i = 0; i < adj[s].size(); i++) {   // calc dp[][1] for every child of s
        int u = adj[s][i];
        if (u == e) continue;
        dp[u][1] = ((ll)(dp[s][1] * pre) % M * post[adj[s].size()-i-1] + 1) % M;
        int v = dp[u][0] + 1;
        pre = ((ll)pre * v) % M;
    }
    for (int u: adj[s]) {       // process children
        if (u == e) continue;
        dfs2(u, s);
    }
}
 
int main() {
    scanf("%d %d", &n, &M);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(0,-1); // calc dp[i][0], rooted at 0
    dp[0][1] = 1;
    dfs2(0,-1); // change root to calc dp[i][1]
 
    for (int i = 0 ; i < n; i++)
        printf("%d\n", ((ll)dp[i][0] * dp[i][1]) % M);
 
    return 0;
}