感觉在找重心的时候错了,然后改了一下求重心的函数,却TLE了,求助大佬为什么是这样:
原来的find:
void find(int x,int tot){
int maxx=0;
size[x]=1,fvis[x]=stp;
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(fvis[y]==stp||fin[y])
continue;
find(y,tot);
size[x]+=size[y];
maxx=max(maxx,size[y]);
}
maxx=max(maxx,tot-size[x]);
if(maxx<minn)
minn=maxx,pos=x;
}
stp++,minn=inf,find(x,sum);
更改后的find:
void find(int x){
int maxx=0;
size[x]=1,fvis[x]=stp,tmp++;
for(int i=start[x];i;i=then[i]){
int y=to[i];
if(fvis[y]==stp||fin[y])
continue;
find(y);
size[x]+=size[y];
maxx=max(maxx,size[y]);
}
maxx=max(maxx,tmp-size[x]);
if(maxx<minn)
minn=maxx,pos=x;
}
stp++,minn=inf,tmp=0,find(x);
给出hack第一个find的数据
1 2
1 3
2 4
2 5
3 6
3 7
3 8
此时找到的第一个重心为3,遍历到1后由于size1=8,所以会将重心错选为1