【换根DP】Subtree

古城微笑少年丶 2024-03-22 22:15 121阅读 0赞

Subtree - 洛谷

题意:

2f05b09dc4aa4486aa9beb190e4cc95f.png

思路:

c69aa721f5f942ae9b567a6372051967.png

01f46b29aa2d457591395189c1390ad6.png

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=1e5+10;
  5. const int mxv=1e5+10;
  6. vector<int> G[mxn];
  7. int N,P,u,v;
  8. int f[mxn],g[mxn],son[mxn],pre[mxn],suf[mxn];
  9. void dfs(int u,int fa){
  10. f[u]=1;
  11. for(auto v:G[u]){
  12. if(v==fa) continue;
  13. dfs(v,u);
  14. f[u]*=(f[v]+1)%P;
  15. f[u]%=P;
  16. }
  17. }
  18. void dfs2(int u,int fa){
  19. if(G[u].size()==1&&G[u][0]==fa) return;
  20. int idx=0;
  21. for(auto v:G[u]){
  22. if(v==fa) continue;
  23. son[++idx]=v;
  24. }
  25. pre[0]=suf[idx+1]=1;
  26. for(int i=1;i<=idx;i++){
  27. pre[i]=pre[i-1]*(f[son[i]]+1)%P;
  28. }
  29. for(int i=idx;i>=1;i--){
  30. suf[i]=suf[i+1]*(f[son[i]]+1)%P;
  31. }
  32. for(int i=1;i<=idx;i++){
  33. g[son[i]]=(pre[i-1]*suf[i+1]%P*g[u]%P+1ll)%P;
  34. }
  35. for(auto v:G[u]){
  36. if(v==fa) continue;
  37. dfs2(v,u);
  38. }
  39. }
  40. void solve(){
  41. cin>>N>>P;
  42. for(int i=1;i<=N-1;i++){
  43. cin>>u>>v;
  44. G[u].push_back(v);
  45. G[v].push_back(u);
  46. }
  47. dfs(1,0);
  48. g[1]=1;
  49. dfs2(1,0);
  50. for(int i=1;i<=N;i++){
  51. cout<<f[i]*g[i]%P<<'\n';
  52. }
  53. }
  54. signed main(){
  55. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  56. int __=1;//cin>>__;
  57. while(__--)solve();return 0;
  58. }

优美版(重生之我是jiangly):

  1. #include <bits/stdc++.h>
  2. using i64 = long long;
  3. using namespace std;
  4. const int N = 1e5 + 10;
  5. const int Inf = 1e18;
  6. vector<int> adj[N];
  7. int m;
  8. int dp[N], dp2[N], num[N];
  9. int pre[N], suf[N];
  10. void dfs1(int u,int fa) {
  11. dp[u] = 1;
  12. for (auto v : adj[u]) {
  13. if (v == fa) continue;
  14. dfs1(v, u);
  15. dp[u] = dp[u] * (dp[v] + 1) % m;
  16. dp[u] %= m;
  17. }
  18. }
  19. void dfs2(int u,int fa) {
  20. if (adj[u].size() == 1 && adj[u][0] == fa) return;
  21. int len = 0;
  22. for (auto v : adj[u]) {
  23. if (v == fa) continue;
  24. num[++len] = v;
  25. }
  26. pre[0] = suf[len + 1] = 1;
  27. for (int i = 1; i <= len; i ++) {
  28. pre[i] = pre[i - 1] * (dp[num[i]] + 1) % m;
  29. }
  30. for (int i = len ; i >= 1; i --) {
  31. suf[i] = suf[i + 1] * (dp[num[i]] + 1) % m;
  32. }
  33. for (int i = 1; i <= len; i ++) {
  34. dp2[num[i]] = (pre[i - 1] * suf[i + 1] %m * dp2[u] %m + 1) % m;
  35. }
  36. for (auto v : adj[u]) {
  37. if (v == fa) continue;
  38. dfs2(v, u);
  39. }
  40. }
  41. void solve() {
  42. int n;
  43. cin >> n >> m;
  44. for (int i = 1; i <= n - 1; i ++) {
  45. int u, v;
  46. cin >> u >> v;
  47. adj[u].push_back(v);
  48. adj[v].push_back(u);
  49. }
  50. dfs1(1, 0);
  51. dp2[1] = 1;
  52. dfs2(1, 0);
  53. for (int i = 1; i <= n; i ++) {
  54. cout << dp2[i] * dp[i] % m << "\n";
  55. }
  56. }
  57. signed main(){
  58. ios::sync_with_stdio(false);
  59. cin.tie(nullptr);
  60. int t = 1;
  61. while (t-- ) {
  62. solve();
  63. }
  64. return 0;
  65. }

发表评论

表情:
评论列表 (有 0 条评论,121人围观)

还没有评论,来说两句吧...

相关阅读