題目
https://gmoj.net/senior/#main/show/6838
題解
這道題目看起來比較奇怪，于是比賽的時候我就沒有管它了，
考慮一個點在最終的圖中分裂了幾次，發現分裂次數等于經過它的次數-1，以起點為根，所走的路徑就是走去很多個子樹內繞一圈回來，然后選擇一個兒子走下去就不回來，在這個兒子處也是這樣子走，
怎么樣才能讓不回傳的點盡可能多呢（顯然一個點回傳它的父親處時，它的父親要分裂一次）？這等價于選擇一條樹上最長簡單路徑，即直徑，
因此這道題只用找出直徑，以它的一個端點為根走，然后對于直徑上的每一個點，都先將它的非直徑上兒子的子樹走完并回傳，接著順著直徑往下走，
CODE
#include<cstdio>
using namespace std;
#define M 205
#define N 105
int f[N][2],son[N][2],fir[N],to[M],nex[M],p[100005],now[N],pre[N],len,node,s;
bool b[N];
inline void inc(int x,int y)
{
to[++s]=y,nex[s]=fir[x],fir[x]=s;
to[++s]=x,nex[s]=fir[y],fir[y]=s;
}
void getd(int k,int fa)
{
for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa)
{
getd(to[i],k);
if(f[to[i]][0]+1>f[k][0])
f[k][1]=f[k][0],son[k][1]=son[k][0],
f[k][0]=f[to[i]][0]+1,son[k][0]=to[i];
else if(f[to[i]][0]+1>f[k][1])
f[k][1]=f[to[i]][0]+1,son[k][1]=to[i];
}
if(f[k][0]+f[k][1]>len) len=f[k][0]+f[k][1],node=k;
}
void dfs(int k,int fa)
{
p[++p[0]]=k;
for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa&&to[i]!=pre[k])
dfs(to[i],k),p[++p[0]]=k;
if(pre[k]) dfs(pre[k],k);
}
int main()
{
freopen("combo.in","r",stdin);
freopen("combo.out","w",stdout);
int root,n,x,y,cnt;
scanf("%d",&n),cnt=n;
for(int i=1;i<n;++i) scanf("%d%d",&x,&y),inc(x,y);
getd(1,0),root=node,b[root]=1;
while(son[root][0]) pre[son[root][0]]=root,root=son[root][0],b[root]=1;
if(son[node][1])
{
pre[node]=x=son[node][1],b[x]=1;
while(son[x][0]) x=pre[x]=son[x][0],b[x]=1;
}
dfs(root,0);
printf("%d\n",p[0]-n);
for(int i=1;i<=p[0];++i)
{
if(!now[p[i]]) now[p[i]]=p[i];
else printf("%d ",now[p[i]]),p[i]=now[p[i]]=++cnt;
}
puts("");
for(int i=1;i<=p[0];++i) printf("%d ",p[i]);
puts("");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200117.html
標籤：python