某一道题,我一开始这样写:
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];
然后就跑得飞快,求大佬解答这是怎么回事啊,正确的点分写法到底怎么搞啊。