Wa #11求调,做法简洁()
查看原帖
Wa #11求调,做法简洁()
365110
xuanyuan_Niubi楼主2021/7/23 21:04

注释里面写得比较清楚了。谢谢大佬呜呜呜。快疯了。

#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+5;
inline int read(){
	char c=getchar();int x=0,f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=0;
	for(;c<='9'&&c>='0';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?x:-x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b^=a^=b;}
//============================================================
struct edge{
	int u,v,nxt;
}ed[M<<2],en[M<<2];
int head[M],cnt_edge,son[M],he[M],cnt_new,fa[M],dep[M];
int depmax,depsec,poimax,poisec,poi;
bool vis_tot[M],vis[M],fl=0;
inline void add_edge(int u,int v){
	ed[++cnt_edge]=(edge){u,v,head[u]};
	head[u]=cnt_edge;son[u]++;
}
inline void change(int x,int no){
	if(x>=depmax)depsec=depmax,depmax=x,poisec=poimax,poimax=no;//如果比最大的还大,那么最大的就是第二大的了, 
	else if(x<depmax&&x>depsec)depsec=x,poisec=no;//如果比第二大的大,那么这个节点就是第二大的了 
}
inline void dfs_son(int x,int fat){
	if(son[x]==1)change(dep[x],x);//是叶子节点才更新,我关注的是节点的编号而不是具体的距离是多少,所以距离是到root的还是end的不重要 
	for(int i=head[x];i;i=ed[i].nxt){
		int v=ed[i].v;
		if(v!=fat&&!vis_tot[v])dfs_son(v,x);//不往回走且不往直径走 
	}
}
inline void dfs_find(int x,int fat){
	fa[x]=fat,dep[x]=dep[fat]+1;//记录fa和dep 
	if(son[x]>=3&&dep[x]>depmax)depmax=dep[x],poi=x;//如果可以作为直径的端点且需要更新才更新 
	for(int i=head[x];i;i=ed[i].nxt){
		int v=ed[i].v;
		if(v!=fat)dfs_find(v,x);
	}
}
//================================================================
int main(){
	int n=read(),root=0;
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add_edge(u,v),add_edge(v,u);
		if(son[u]>=3)root=u;
		if(son[v]>=3)root=v;
	}
//	for(int i=1;i<=cnt_new;i++)printf("%d %d\n",en[i].u,en[i].v);
	//我发现没有必要建新图了,因为两个端点的链上可以有两个儿子,如果只将有三个儿子的点加入新图,可能会“断” 
	//要做的就是遍历找直径的时候只将有三个儿子的点作为终点,这样就可以找到两个端点(其实我们只需要找到两个端点就够了) 
	dfs_find(root,0);
	root=poi;depmax=0;dep[root]=0;
	dfs_find(root,0);//
	int end=poi;depmax=0;//前面是找以儿子个数大于2个的节点建的新树的直径两个端点,分别是 root和end;
	while(poi!=root){
		vis_tot[poi]=1;poi=fa[poi];//标记直径上的点,防止遍历子树的时候往上跑了 
	}
	dfs_son(root,0);
	int t1=poimax,t2=poisec;//记录这一个子树的最深两个点 
	depmax=depsec=0;
	dfs_son(end,fa[end]); 
	printf("%d %d\n%d %d",t1,poimax,t2,poisec);
	return 0;
}
2021/7/23 21:04
加载中...