題意：

有一顆樹，每條邊是好邊或者是壞邊，對于一個節點為x，如果任意一個點到x的路徑上的壞邊不超過1條，那么這樣的方案是合法的，求所有合法的方案數。

對于n個所有可能的x，輸出n個答案。

分析：

題解

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 200000 + 10; 9 const int MOD = 1000000007; 10 int n; 11 12 vector<int> G[maxn], pre[maxn], suf[maxn]; 13 14 void scan(int& x) 15 { 16 x = 0; 17 char c = ' '; 18 while(c < '0' || c > '9') c = getchar(); 19 while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } 20 } 21 22 int d[maxn], f[maxn]; 23 24 void mul(int& x, int y) { x = 1LL * x * y % MOD; } 25 26 void dfs(int u) 27 { 28 d[u] = 1; 29 int sz = G[u].size(); 30 for(int i = 0; i < sz; i++) 31 { 32 int v = G[u][i]; 33 dfs(v); 34 mul(d[u], d[v] + 1); 35 } 36 37 int p = 1, s = 1; 38 for(int i = 0; i < sz; i++) 39 { 40 mul(p, d[G[u][i]] + 1); 41 mul(s, d[G[u][sz-1-i]] + 1); 42 pre[u].push_back(p); 43 suf[u].push_back(s); 44 } 45 46 reverse(suf[u].begin(), suf[u].end()); 47 } 48 49 void dfs2(int u) 50 { 51 int sz = G[u].size(); 52 for(int i = 0; i < sz; i++) 53 { 54 int v = G[u][i]; 55 f[v] = f[u]; 56 if(i > 0) mul(f[v], pre[u][i - 1]); 57 if(i < sz - 1) mul(f[v], suf[u][i + 1]); 58 f[v]++; 59 if(f[v] >= MOD) f[v] -= MOD; 60 dfs2(v); 61 } 62 } 63 64 int main() 65 { 66 scanf("%d", &n); 67 for(int x, i = 2; i <= n; i++) 68 { 69 scan(x); 70 G[x].push_back(i); 71 } 72 73 dfs(1); 74 f[1] = 1; 75 dfs2(1); 76 77 for(int i = 1; i <= n; i++) printf("%I64d ", 1LL * d[i] * f[i] % MOD); 78 79 return 0; 80 } 代碼君

?

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4755263.html

總結

以上是生活随笔為你收集整理的CodeForces 543D 树形DP Road Improvement的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。