Description
Input
Output
Sample Input
输入1： 2 1 2 3 输入2： 5 1 2 2 1 3 3 2 4 4 2 5 5
Sample Output
输出1: 6 2 1 输出2： 32 2 1 4 5 3
Data Constraint
首先Ans=dep[i]+dep[p[i]]-2*dep[lca(i,p[i])];
易证当根为重心时Ans取最小值，我们只需要求字典序最小。
接下来就是一个二分图匹配的问题，首先我们贪心的选择。但在某些时候我们不能这样选，当一棵子树未匹配数过多时（即到以后只能自己匹配自己时）我们要优先匹配该树中的点。
那么什么时候是过多呢╮(╯▽╰)╭
我们设L[i]为i子树左边未匹配的点数，R[i]为右边未匹配的点数。
那么当L[i]>Rsum-R[i]时会出现过多的情况，
两边同时加上R[i]变为L[i]+R[i]>Rsum
我们只需用一棵线段树记录L[i]+R[i]看是否出现以上情况即可
#include#include #include #include #include #include using namespace std;typedef long long ll;priority_queue H[100011];struct Tree{ int mn,mx,id;}tr[600011];Tree emp;int bel[100011],g[100011],next[200022],y[200022],que[100011],len[200011];ll dis[100011];int mx[100011],size[100011],fa[100011],ans[100011],sz[100011];ll Ans;int n,i,x,z,q,root,tot,tt;void star(int i,int j,int k){ tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; len[tt]=k;}void Bfs(int st){ int l,r,x,j,k; memset(size,0,sizeof(size)); memset(dis,0,sizeof(dis)); memset(fa,0,sizeof(fa)); l=r=1; que[l]=st; while(l<=r){ x=que[l]; j=g[x]; while(j!=0){ k=y[j]; if(k!=fa[x]){ fa[k]=x; r++; que[r]=k; dis[k]=dis[x]+len[j]; } j=next[j]; } l++; } for(i=n;i>=1;i--){ x=que[i]; size[x]++; mx[x]=max(mx[x],n-size[x]); if(mx[x]<=n/2)root=x; size[fa[x]]+=size[x]; mx[fa[x]]=max(mx[fa[x]],size[x]); }}void dfs(int x){ int j,k; bel[x]=tot; sz[tot]++; H[tot].push(-x); j=g[x]; while(j!=0){ k=y[j]; if(k!=fa[x])dfs(k); j=next[j]; }}void Prepare(){ int j,k; bel[root]=1; H[1].push(-root); tot=1; sz[1]=1; j=g[root]; while(j!=0){ k=y[j]; tot++; dfs(k); j=next[j]; }}Tree Merge(Tree a,Tree b){ Tree c; c.mn=min(a.mn,b.mn); if(a.mx>b.mx){ c.mx=a.mx; c.id=a.id; } else{ c.mx=b.mx; c.id=b.id; } return c;}void build(int l,int r,int t){ if(l==r){ tr[t].mn=-H[l].top(); if(l!=1)tr[t].mx=sz[l]*2; else tr[t].mx=0; tr[t].id=l; return; } int mid; mid=(l+r)/2; build(l,mid,t+t); build(mid+1,r,t+t+1); tr[t]=Merge(tr[t+t],tr[t+t+1]);}void insert(int t,int l,int r,int x,int y,int z){ if(l==r){ if(z==0)tr[t].mx+=y; else tr[t].mn=y; return; } int mid; mid=(l+r)/2; if(x<=mid)insert(t+t,l,mid,x,y,z); if(x>mid)insert(t+t+1,mid+1,r,x,y,z); tr[t]=Merge(tr[t+t],tr[t+t+1]);}Tree ask(int t,int l,int r,int x,int y){ if(x>y)return emp; if(l==x&&r==y)return tr[t]; int mid; mid=(l+r)/2; if(y<=mid)return ask(t+t,l,mid,x,y); if(x>mid)return ask(t+t+1,mid+1,r,x,y); if(x<=mid&&y>mid)return Merge(ask(t+t,l,mid,x,mid),ask(t+t+1,mid+1,r,mid+1,y));}void Work(){ int i,mi,mn,sum; Tree Tl,Tr; for(i=1;i<=n;i++)Ans+=dis[i]; Ans*=2; printf("%I64d\n",Ans); build(1,tot,1); sum=n; emp.mn=2147483646; for(i=1;i<=n;i++){ if(bel[i]!=1){ Tl=ask(1,1,tot,1,bel[i]-1); Tr=ask(1,1,tot,bel[i]+1,tot); mn=min(Tl.mn,Tr.mn); } else mn=tr[1].mn; insert(1,1,tot,bel[i],-1,0); insert(1,1,tot,bel[mn],-1,0); if(tr[1].mx>sum-1){ mi=tr[1].id; insert(1,1,tot,bel[mn],1,0); insert(1,1,tot,mi,-1,0); ans[i]=-H[mi].top(); H[mi].pop(); if(!H[mi].empty())insert(1,1,tot,mi,-H[mi].top(),1); else insert(1,1,tot,mi,2147483646,1); } else{ ans[i]=mn; H[bel[mn]].pop(); if(!H[bel[mn]].empty())insert(1,1,tot,bel[mn],-H[bel[mn]].top(),1); else insert(1,1,tot,bel[mn],2147483646,1); } sum--; } for(i=1;i