当前位置:   article > 正文

E. Tree Painting(换根)_c - tree painting

c - tree painting
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #define ll long long
  5. using namespace std;
  6. vector<int> g[1008611];
  7. int v;
  8. int n,siz[1008611];
  9. ll up[1008611], sum[1008611];
  10. void init(int u,int f) {
  11. siz[u]=1;
  12. for(auto v:g[u]) {
  13. if(v==f) continue;
  14. init(v,u);
  15. siz[u] += siz[v];
  16. sum[u] += sum[v] + siz[v];
  17. }
  18. }
  19. void dfs(int u,int f,int root) {
  20. if (f != u) {
  21. up[u] = up[f] + siz[root] + sum[f] - sum[u] - 2*siz[u];
  22. }
  23. for(auto v: g[u]) {
  24. if(v==f) continue;
  25. dfs(v,u,root);
  26. }
  27. }
  28. int main() {
  29. cin>>n;
  30. for(int i=1;i<=n;i++) {
  31. g[i].clear();
  32. }
  33. for(int i=1;i<n;i++){
  34. int u,v;
  35. cin>>u>>v;
  36. g[u].push_back(v);
  37. g[v].push_back(u);
  38. }
  39. init(1,1);
  40. dfs(1,1,1);
  41. ll ans = 0;
  42. for(int i=1;i<=n;i++)
  43. ans=max(ans,up[i]+sum[i]);
  44. cout <<ans+n<< endl;
  45. return 0;
  46. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/75109
推荐阅读
相关标签
  

闽ICP备14008679号