赞
踩
- #include <iostream>
- #include <vector>
- #include <cstring>
- #define ll long long
- using namespace std;
- vector<int> g[1008611];
- int v;
- int n,siz[1008611];
- ll up[1008611], sum[1008611];
- void init(int u,int f) {
- siz[u]=1;
- for(auto v:g[u]) {
- if(v==f) continue;
- init(v,u);
- siz[u] += siz[v];
- sum[u] += sum[v] + siz[v];
- }
- }
- void dfs(int u,int f,int root) {
- if (f != u) {
- up[u] = up[f] + siz[root] + sum[f] - sum[u] - 2*siz[u];
- }
- for(auto v: g[u]) {
- if(v==f) continue;
- dfs(v,u,root);
- }
- }
- int main() {
- cin>>n;
- for(int i=1;i<=n;i++) {
- g[i].clear();
- }
- for(int i=1;i<n;i++){
- int u,v;
- cin>>u>>v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- init(1,1);
- dfs(1,1,1);
- ll ans = 0;
- for(int i=1;i<=n;i++)
- ans=max(ans,up[i]+sum[i]);
- cout <<ans+n<< endl;
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。