受到commonc的感召（其实并不是他感召我而是我不知道该做些啥-_-），我们也来开始做POI
这题……额，题解写到这了结果发现刚交上去的wa了-_-
额……恩……结果就又调了将近一个小时，然后发现判断若以这个点为根是否有一个大小为n/2的子树要在更新从父亲过来的最长路之前写……
-_-
诶呀还是开始说题解把……发现答案就是所有点的深度和*2再减去以根为起点最长路的长度，然后发现无解条件是以其为根有一个子树大小大于n/2
但是还有特殊情况，当n为偶数且以其为根有一个子树大小等于n/2时，那么这个最长路只能在大小为n/2的子树里选……
然后就是树DP，维护一下深度和，子树大小，最长次长路什么的……注意要强制最长次长路不是往一个子树里走的……
嗯……感觉代码又长又丑-_-
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 1000010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long struct vec{ int to; int fro; }; vec mp[MAXN*2]; int tai[MAXN],cnt; int siz[MAXN],bal[MAXN],dep[MAXN],mx[MAXN],mx1[MAXN],mxt[MAXN]; ll sum[MAXN]; int rt; int n; inline void be(int x,int y){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; } inline void bde(int x,int y){ be(x,y); be(y,x); } void dfs(int x,int f){ int i,y; dep[x]=dep[f]+1; siz[x]=1; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(y!=f){ dfs(y,x); bal[x]=max(bal[x],siz[y]); sum[x]+=sum[y]+siz[y]; siz[x]+=siz[y]; if(mx[y]+1>=mx[x]){ mx1[x]=mx[x]; mx[x]=mx[y]+1; }else if(mx[y]+1>=mx1[x]){ mx1[x]=mx[y]+1; } } } bal[x]=max(bal[x],n-siz[x]); } void dp(int x,int f){ int i,y; if(!(n&1)&&bal[x]==n/2){ if(bal[x]==n-siz[x]){ if(mx[x]+1==mx[f]){ mxt[x]=mx1[f]+1; }else{ mxt[x]=mx[f]+1; } }else{ for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(siz[y]==bal[x]){ mxt[x]=mx[y]+1; } } } } if(f){ sum[x]=sum[f]+n-2*siz[x]; int t; if(mx[x]+1==mx[f]){ t=mx1[f]+1; }else{ t=mx[f]+1; } if(t>=mx[x]){ mx1[x]=mx[x]; mx[x]=t; }else if(t>=mx1[x]){ mx1[x]=t; } } for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(y!=f){ dp(y,x); } } } int main(){ /* freopen("ins1f.in","r",stdin); freopen("dui.txt","w",stdout); //*/ int i,x,y; scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); bde(x,y); } dfs(1,0); dp(1,0); for(i=1;i<=n;i++){ if(mxt[i]){ mx[i]=mxt[i]; } if(bal[i]>n/2){ printf("-1\n"); }else{ printf("%lld\n",sum[i]*2-mx[i]); } } return 0; } /* 5 2 1 3 2 4 3 5 3 */