换根dpWA 20PTS求调
查看原帖
换根dpWA 20PTS求调
591179
huangyuxaing楼主2023/10/4 20:39

码风良好,求大佬帮调

#include<bits/stdc++.h>
using namespace std;
const int M=2e6+7;
int n,eid,p[M],pre[M],flag[M],son1[M],son2[M],tot[M],dp[M],ans,a,b;
struct edge{
	int u,v,next;
}e[M];
void insert(int u,int v){
	e[++eid].u=u;e[eid].v=v;
	e[eid].next=p[u];p[u]=eid;
}
void dfs1(int u,int fa){
	//cout<<u<<endl;
	for(int i=p[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		dfs1(v,u);
		tot[u]++;
		if(pre[v]>=pre[son1[u]])son1[u]=v;
		else if(pre[v]>=pre[son2[u]])son2[u]=v;
	}
	pre[u]=pre[son1[u]]+tot[u];
	if(!pre[u])pre[u]++;
}
void dfs2(int u,int fa){
	if(flag[fa]&&(u==son1[fa]||u==son2[fa]))dp[u]=dp[fa];
	else dp[u]=dp[fa]-pre[son1[fa]]+pre[u];
	if(pre[son1[u]]+pre[son2[u]]+tot[u]-1>dp[u]){
		dp[u]=pre[son1[u]]+pre[son2[u]]+tot[u]-1;
		flag[u]=1;
	}
	//cout<<dp[u]<<" "<<u<<" "<<pre[u]<<" "<<son1[u]<<" "<<son2[u]<<" "<<tot[u]<<endl;
	ans=max(ans,dp[u]);
	for(int i=p[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		dfs2(v,u);
	}
}
int main(){
	scanf("%d%*d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		insert(a,b);insert(b,a);
	}
	dfs1(1,0);
	dfs2(1,0);
	printf("%d\n",ans);
	return 0;
}
2023/10/4 20:39
加载中...