关于淀粉质找重心
  • 板块学术版
  • 楼主The_Elation_Aha
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/3/16 11:46
  • 上次更新2024/3/16 14:33:59
查看原帖
关于淀粉质找重心
998639
The_Elation_Aha楼主2024/3/16 11:46

某一道题,我一开始这样写:

void findrt(ll u,ll fa){
	siz[u]=1,maxp[u]=0;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa||vis[v]) continue;
		findrt(v,u);
		siz[u]+=siz[v];
		maxp[u]=max(maxp[u],siz[v]);
	}
	maxp[u]=max(maxp[u],sum-siz[u]);
	if(maxp[u]<maxp[rt]) rt=u;
}

分治里面初始化:rt=v,maxp[rt]=sum=siz[v];

然后TLE,之后换成这样:

ll msiz=0;
void findrt(ll u,ll fa){
	siz[u]=1;
	ll maxn=0;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa||vis[v]) continue;
		findrt(v,u);
		siz[u]+=siz[v];
		maxn=max(maxn,siz[v]);
	}
	maxn=max(maxn,sum-siz[u]);
	if(maxn<msiz) msiz=maxn,rt=u;
}
初始化:msiz=sum=siz[v];

然后就跑得飞快,求大佬解答这是怎么回事啊,正确的点分写法到底怎么搞啊。

2024/3/16 11:46
加载中...