[ATdp v] Subtree
思路
不难想到令 \(f_u\) 表示 \(u\) 子树内满足条件的答案数。
有
\[f_{u} = \prod_{v\in son_{u}}(f_v + 1)
\]
然后换根求出 \(g\) 表示整棵树里的答案：
\[g_u = (\dfrac{g_{fa}}{f_u + 1} + 1)f_u
\]
但是你会发现取模之后不一定有逆元，很尴尬。
所以如果把 \(f_u\) 拿出来，\(g\) 就表示子树外的答案，有转移：
\[g_u = g_{fa} \cdot\dfrac{f_{fa}}{f_u + 1} + 1\\
g_u = g_{fa} \cdot\prod_{v\in son_{fa}\vee v\ne u}(f_v + 1) + 1\\
\]
这样就没有除法了，对 \(fa\) 的儿子进行前/后缀积就得到了 \(O(n)\) 的算法。
// Problem: Subtree
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-12-23 15:16:14
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, f[N], g[N], s[N], mod;
vector<int> G[N];
void dfs(int u, int fa) {
f[u] = 1;
for(auto v : G[u]) {
if(v == fa) continue;
dfs(v, u);
f[u] = 1ll * f[u] * (f[v] + 1) % mod;
}
}
void dfs2(int u, int fa) {
s[G[u].size()] = 1;
for(int i = (int)G[u].size() - 1, v; i >= 0; i --) {
v = G[u][i];
if(v == fa) s[i] = s[i + 1];
else s[i] = 1ll * s[i + 1] * (f[v] + 1) % mod;
}
int sum = 1;
for(int i = 0, v; i < G[u].size(); i ++) {
v = G[u][i];
if(v == fa) continue;
g[v] = 1ll * sum * s[i + 1] % mod * g[u] % mod + 1;
sum = 1ll * sum * (f[v] + 1) % mod;
}
for(auto v : G[u])
if(v != fa) dfs2(v, u);
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> mod;
for(int i = 1, a, b; i < n; i ++) {
cin >> a >> b;
G[a].push_back(b), G[b].push_back(a);
}
dfs(1, 1), g[1] = 1, dfs2(1, 1);
for(int i = 1; i <= n; i ++)
cout << (1ll * g[i] * f[i] % mod) << '\n';
return 0;
}