萌新刚学dp求助,WA on Test 22
查看原帖
萌新刚学dp求助,WA on Test 22
135258
charm1楼主2021/10/14 19:44
#include <bits/stdc++.h>
#define pii pair <int,int> 
using namespace std;
const int maxn=200005;
int n,cnt;
int head[maxn];
int dp[maxn][3],d1[maxn][3],pre[maxn],d2[maxn];
struct edge{
	int v,nxt;
}a[maxn<<1];
inline void add(int x,int y){
	++cnt;
	a[cnt].v=y;
	a[cnt].nxt=head[x];
	head[x]=cnt;
} 
inline int read(){
	int ret=0,f=1;	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void insert(int x,int w,int d){
	if(w>dp[x][0]){
		swap(dp[x][1],dp[x][2]);
		swap(d1[x][1],d1[x][2]);
		swap(dp[x][1],dp[x][0]);
		swap(d1[x][1],d1[x][0]);
		dp[x][0]=w;
		d1[x][0]=d;
		return;
	}
	if(w>dp[x][1]){
		swap(dp[x][1],dp[x][2]);
		swap(d1[x][1],d1[x][2]);
		dp[x][1]=w;
		d1[x][1]=d;
		return;
	}
	if(w>dp[x][2]){
		dp[x][2]=w;
		d1[x][2]=d;
		return;
	}
}
void dfs1(int x,int f){
	d1[x][0]=x; dp[x][1]=dp[x][2]=-1;
	for(int k=head[x];k;k=a[k].nxt){
		int v=a[k].v;
		if(v==f) continue;
		dfs1(v,x);
		insert(x,dp[v][0]+1,d1[v][0]);
	}
}
void dfs2(int x,int f){
	int p1=pre[x]+1,p2=dp[x][0]+1,p3=dp[x][1]+1;
	int n1=d2[x],n2=d1[x][0],n3=dp[x][1];
	for(int k=head[x];k;k=a[k].nxt){
		int v=a[k].v;
		if(v==f) continue;
		if(d1[v][0]!=n2){
			if(p1>p2){
				pre[v]=p1;
				d2[v]=n1;
			}
			else{
				pre[v]=p2;
				d2[v]=n2;
			}
		}
		else{
			if(p1>p3||n3==0){
				pre[v]=p1;
				d2[v]=n1;
			}
			else{
				pre[v]=p3;
				d2[v]=n3;
			}
		}
		dfs2(v,x);
	}
	insert(x,pre[x],d2[x]);
}
void scan(){
	n=read();
	for(int k=1;k<n;k++){
		int x,y;
		x=read(); y=read();
		add(x,y); add(y,x);
	}
}
void solve(){
	dfs1(1,0);
//	for(int k=1;k<=n;k++)
//	cout<<d1[k][0]<<" "<<d1[k][1]<<" "<<d1[k][2]<<endl;
//	puts("");
//	for(int k=1;k<=n;k++)
//	cout<<dp[k][0]<<" "<<dp[k][1]<<" "<<dp[k][2]<<endl;
//	puts("");	
	pre[1]=0; d2[1]=1;
	dfs2(1,0);
	int ans=0,w=0;
	for(int k=1;k<=n;k++)
	if(dp[k][0]+dp[k][1]+dp[k][2]>w){
		w=dp[k][0]+dp[k][1]+dp[k][2];
		ans=k;
	}
	printf("%d\n",w);
	printf("%d %d %d\n",d1[ans][0],d1[ans][1],d1[ans][2]);
}
signed main(){
	scan(); solve();
	return 0;
}
2021/10/14 19:44
加载中...