GMOJ 6838. 【2020.10.31提高组模拟】小j的组合

GMOJ 6838. 【2020.10.31提高组模拟】小j的组合

题目描述

题解

这应该是这场比赛最水的一题，但我没切。

做法很简单，可以发现，进行一次操作，相当于是可以将某一个点多经过一次，感性理解。

然后找出直径，其他的点最终都要回到直径上，(dfs)统计答案即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300
using namespace std;
int n,x,y,i,g,q[N],tot,dis[N],xp,yp,mx,ans1[N],ans2[N],bz[N],num,f[N],id[N];
struct edge{
	int to,next;
}e[N];
void insert(int x,int y){
	tot++;
	e[tot].to=y;
	e[tot].next=q[x];
	q[x]=tot;
}
void dfs(int x,int father){
	int i,y;
	f[x]=dis[x];id[x]=x;
	for (i=q[x];i;i=e[i].next){
		y=e[i].to;
		if (y!=father){
			dis[y]=dis[x]+1;
			dfs(y,x);
			if (f[y]>f[x]){
				id[x]=y;
				f[x]=f[y];
			}
		}
	}
}
void dfs1(int x,int pl){
	int i,j,y,sp=0;
	bz[x]=1;
	ans2[++ans2[0]]=x;
	if (id[x]==x) return;
	if (pl==0){
		for (i=q[x];i;i=e[i].next){
			y=e[i].to;
			if (bz[y]==0&&id[x]!=y){
				dfs1(y,1);
				ans1[++ans1[0]]=x;
				ans2[++ans2[0]]=n+ans1[0];
			}
		}
		dfs1(id[x],0);
	}
	else{
		for (i=q[x];i;i=e[i].next){
			y=e[i].to;
			if (bz[y]==0){
				dfs1(y,1);
				ans1[++ans1[0]]=x;
				ans2[++ans2[0]]=n+ans1[0];
			}
		}
	}
}
int main(){
	freopen("combo.in","r",stdin);
	freopen("combo.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<n;i++)
		scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
	dfs(1,0);
	for (i=1;i<=n;i++) if (dis[i]>mx) mx=dis[i],xp=i;
	memset(dis,0,sizeof(dis));
	memset(f,0,sizeof(f));
	dfs(xp,0);
	mx=0;
	for (i=1;i<=n;i++) if (dis[i]>mx) mx=dis[i],yp=i;
	mx++;g=n-mx;
	printf("%d
",g);
	dfs1(xp,0);
	for (i=1;i<=g;i++)
		printf("%d ",ans1[i]);
	printf("
");
	for (i=1;i<=n+g;i++)
		printf("%d ",ans2[i]);
	printf("
");
	return 0;
}