# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
974400 | sleepntsheep | Village (BOI20_village) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#define N 100000
#define M (2*N)
int n, p1[N],head[N], nxt[M], vv[M], eo = 1, tin[N], timer, aux[N],sz[N],qu[N],qh,qt,deg[N];
void link(int u,int v)
{
int i = eo++;
nxt[i]=head[u],vv[i]=v,head[u]=i;
++deg[v];
}
long long max, min;
void dfs(int u,int p)
{
sz[u]=1;
aux[tin[u] = timer++] = u;
for (int j =head[u];j;j=nxt[j])if(p!=vv[j]){
dfs(vv[j],u);
max+=sz[vv[j]]<(n-sz[vv[j]])?sz[vv[j]]:n-sz[vv[j]];
sz[u]+=sz[vv[j]];
}
}
int main()
{
scanf("%d",&n);
for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),link(--u,--v),link(v,u);
dfs(0,0);
for(int i=0;i<n;++i)p1[i]=i;
for(int i=0;i<n;++i)if(indeg[i]==1)qu[qh++]=i;
while(qh-qt)
{
int u=qu[qt++],f=0;
for(int j=head[u];j;j=nxt[j])
{
int temp,v=vv[j];
if(--deg[v]==1){
qu[qh++]=v;
min+=2;
f=1;
temp=p1[u],p1[u]=p1[v],p1[v]=temp;
break;
}
}
if(!f)
{
int v=vv[head[u]];
temp=p1[u],p1[u]=p1[v],p1[v]=temp;
min+=2;
}
}
printf("%lld %lld\n",min,max<<1);
for(int i=0;i<n;++i)
printf("%d ",1+p1[i]);
putchar(10);
for(int i=0;i<n;++i)
printf("%d ",1+aux[(tin[i]+n/2)%n]);
}