TopCoder srm683 div2 1000

2024-01-28 05:58

文章标签 div2 1000 topcoder srm683

本文主要是介绍TopCoder srm683 div2 1000，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

已经弱到去div2混了……
题意：给一棵无根树，计算它的所有子树的大小的和。
这个问题转化为统计每个节点的“贡献”，即它在所有可能的子树中出现了多少次。还是先拿有根树来考虑，假设我们已经计算出了树t所有节点的“贡献”，如果在t中的某个叶子v上，连接一棵新的子树t’会怎么样呢？这样一来，v的贡献会将会被乘上“子树t’的树根的贡献+1”。于是，我们可以通过dfs，计算出以每个节点为根的子树中，该节点的“贡献”。
因为整棵树的根没有父节点，它的答案就是前面计算的值。对于其他节点，我们也同样应该把它们转化为根考虑，我们可以“砍断”它与父节点相连的边，再把父节点当成儿子加入（根据之前计算与逆元来完成），这个过程需要第二次dfs。
具体还是看代码容易理解。

#include <bits/stdc++.h>
#include <unordered_map> using namespace std;#define ll long longint a[100010];const int mod = 1e9+7;void ExEuclid(ll a,ll b,ll &x,ll &y,ll &q){      if(b==0){      x=1;y=0;q=a;      return;      }      ExEuclid(b,a%b,y,x,q);      y-=x*(a/b);      
}      ll inv(ll num){      ll x,y,q;      ExEuclid(num,mod,x,y,q);      if(q==1)return (x+mod)%mod;else return 0;  
}vector<int> adj[100010];
int p[100010];
ll ans[100010];ll dfs(int u,int pre){int sz=adj[u].size();ans[u] = 1;for(int i = 0;i<sz;i++){int v = adj[u][i];if(v==pre)continue;p[v]=u;ans[u]*=(dfs(v,u)+1);ans[u]%=mod;}return ans[u];
}ll res = 0;void dfs2(int u,int pre){int sz=adj[u].size();if(u==0){res+=ans[u];}else{ans[u] = ans[u] * (  ((ans[p[u]]*inv(ans[u]+1) )%mod+1)%mod )%mod;res+=ans[u];res%=mod;}for(int i = 0;i<sz;i++){int v = adj[u][i];if(v==pre)continue;dfs2(v,u);}
}class SubtreesCounting{
public:int sumOfSizes(int n, int a0, int b, int c, int m){a[0] = a0;for(int i=1;i<=n-2;i++){a[i] = ( (b+0LL) * a[i-1] + c) % m;}for(int i=1;i<=n-1;i++){int j = a[i-1] % i;adj[i].push_back(j);adj[j].push_back(i);}dfs(0,-1);dfs2(0,-1);return (int)res;}
};