rt,刚刚想把这题代码改改交到别的地方,结果发现一直t,拿到本地编译了一下,报了个 warning,才发这题我在求重心时,所用的 sz 数组都是没有初始化的!!!
void calsz(int p,int fa){
sz[p]=1;
for(int i=0,nx;i<(int)e[p].size();i++){
//此处nx没有赋值,甚至没有初始化,正常应该赋值为e[p][i].fi
if(vis[nx] || nx==fa)continue;
calsz(nx,p);
sz[p]+=sz[nx];
}
}
int calrt(int p,int fa,int tot){
bool f=(tot<=(sz[p]<<1));
for(int tmp,nx,i=0;i<(int)e[p].size();i++){
nx=e[p][i].fi;
if(vis[nx] || nx==fa)continue;
f&=(tot>=(sz[nx]<<1));
tmp=calrt(nx,p,tot);
if(~tmp)return tmp;
}
return f?p:-1;
}