这个tree它会卡一些奇怪的东西,可能取模出来0让结果出错,所以特判暴力以下,希望大佬帮我看看是不是卡过去的。。。。
p是x的儿子
换根DP,第一次dp[x] *= (dp[p] + 1);第二次 根换成儿子----ans = dp[x] / (dp[p] + 1),再把儿子加上根 dp[p] *= (ans + 1);这里(dp[p] + 1) %mod 1e9+7 可能等于0,
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn = 1e6 + 11; typedef long long ll; ll mod = 1e9 + 7; ll dp[maxn]; ll list[maxn]; vector<int >G[maxn]; void add(int x, int y) { G[x].push_back(y); } ll k_q(ll a, ll b) { ll res = 1; while (b) { if (b & 1) { if((res*a)%mod != 0) res = (res*a) % mod; } b >>= 1; if((a*a)%mod != 0) a = (a*a) % mod; } return res; } int dfs1(int x, int fa,ll *cns) { cns[x] = 1; for (int i = 0; i < G[x].size(); i++) { int p = G[x][i]; if (p == fa) continue; dfs1(p, x, cns); cns[x] = (cns[x] * (cns[p] + 1)) % mod; } return 0; } //a * c^(p-2) mod p==(a/c) % p int dfs2(int x, int fa) { for (int i = 0; i < G[x].size(); i++) { int p = G[x][i]; if (p == fa) continue; ll ans; if ((dp[p] + 1) % mod == 0) { dfs1(p, -1, list); dp[p] = list[p]; } else { ans = (dp[x] * k_q(dp[p] + 1, mod - 2)) % mod; dp[p] = (dp[p] * (ans + 1)) % mod; } dfs2(p, x); } return 0; } int main() { int n; scanf("%d", &n); //for (int i = 1; i <= n; i++) dp[i] = 1; for (int i = 1; i < n; i++) { int x, y; scanf("%d %d", &x, &y); add(x, y); add(y, x); } dfs1(1, -1, dp); dfs2(1, -1); for (int i = 1; i <= n; i++) { printf("%lld\n", dp[i]); } return 0; }