RT。请看下面代码的注释部分:
void solve(int k)
{
vis[k] = 1;
calc(k);
for(int i = h[k];~i;i = ne[i])
{
int nx = e[i];
if(vis[nx])
continue;
root = 0;
get_root(nx,0,sz[nx]);
solve(root);
}
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
for(int i = 1,x,y,z;i < n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for(int i = 1;i <= m;i++)
scanf("%d",&q[i]);
maxp[0] = n;
get_root(1,0,n);
get_root(root,0,n);
solve(root);
for(int i = 1;i <= m;i++)
printf("%s\n",ok[i] ? "AYE" : "NAY");
return 0;
}
在许多的题解中 "2" 这行是不需要加的。但根据Agoh大佬在B站的说法,"1"中算出的sz是以节点 1 为根的子树大小,会影响"3"带来的复杂度,所以加上"2"算出"sz"的就是以 root 为根的大小。
然后……运行时间还多了5ms……
所以有没有必要加上"2"呢?