题解：P12534 [XJTUPC 2025] 奥日

这题其实这么说吧，分几个步骤

1 找树的直径，要得到直径长度之余，还要用一个bool数组把树的直径上的点都标记起来。

2 最后要输出的m值的数量等于ans.size()+k*2，ans是存放直径的点的vector，并且k=min(k,n-ans.size());也就是说，k要先比小，防止点没k多的情况

3 然后就可以用一个for循环+dfs方法，去输出这条最终路径
  这部分倒是很简单
  for(int cu:ans){
			dfs(cu,0);
	}
void dfs(int cu,int fa){
	cout<<cu<<" ";
	for(int i=head[cu];i;i=e[i].nxt){
		int to=e[i].to;
		if(vis[to]||to==fa)continue;
//		if(to==fa)
		if(k){
			k--;
			dfs(to,cu);
			cout<<cu<<" ";
		}
	}
}

完整代码如下
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int MXN1=2e5+10;
struct edge{
	int nxt,to;
} e[MXN1*2];
int cnt;
int head[MXN1];
void add(int from,int to){
	cnt++;
	e[cnt].nxt=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
int n,k;

int shendu[MXN1];
int path[MXN1];
bool vis[MXN1];
vector<int> ans;
void dfs1(int cu,int fa,int &zy,int &zhongd){
	for(int i=head[cu];i;i=e[i].nxt){
		if(e[i].to!=fa){
			shendu[e[i].to]=shendu[cu]+1;
			path[e[i].to]=cu;
			if(shendu[e[i].to]>zy){
				zy=shendu[e[i].to];
				zhongd=e[i].to;
			}
			dfs1(e[i].to,cu,zy,zhongd);
//			cout<<cu<<endl;
		}
	}
}
void dfs(int cu,int fa){
	cout<<cu<<" ";
	for(int i=head[cu];i;i=e[i].nxt){
		int to=e[i].to;
		if(vis[to]||to==fa)continue;
//		if(to==fa)
		if(k){
			k--;
			dfs(to,cu);
			cout<<cu<<" ";
		}
	}
}
int t;
int main(){
//	freopen("task11.in","r",stdin);
	cin>>t;
	while(t--){
		cnt=0;
		memset(head,0,sizeof(head));
		memset(vis,0,sizeof(vis));
		memset(e,0,sizeof(e));
		ans.clear();
		cin>>n>>k;
		for(int i=1;i<n;i++){
			int st,ed;cin>>st>>ed;
			add(st,ed),add(ed,st);
		}
		int st=1,zy=0,zhongd=0;
		shendu[st]=0;
		dfs1(st,0,zy,zhongd);
		
		st=zhongd,zy=0,zhongd=0;
		shendu[st]=0,path[st]=0;
		dfs1(st,0,zy,zhongd);

do{

ans.push_back(zhongd);
			vis[zhongd]=true;
			zhongd=path[zhongd];		
		} while(zhongd!=0);
		int sy=n-ans.size();
		k=min(k,n-ans.size());
		cout<<ans.size()+k*2<<endl;
		for(int cu:ans){
			dfs(cu,0);
		}		
		cout<<endl;
	}

}

正在渲染内容...