ningago @ 2022-06-07 17:48:49
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]);//"3"
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);//"1"
get_root(root,0,n);//"2"
solve(root);
for(int i = 1;i <= m;i++)
printf("%s\n",ok[i] ? "AYE" : "NAY");
return 0;
}
在许多的题解中 "2"
这行是不需要加的。但根据Agoh大佬在B站的说法,"1"
中算出的sz
是以节点 "3"
带来的复杂度,所以加上"2"
算出"sz"
的就是以
然后……运行时间还多了5ms……
所以有没有必要加上"2"
呢?
by gxy001 @ 2022-06-07 18:01:55
@ningago http://liu-cheng-ao.blog.uoj.ac/blog/2969
by liqingyang @ 2022-06-07 18:02:01
不加时间复杂度好像也是对的,但是加的时间复杂度对得一目了然
by ningago @ 2022-06-07 18:05:23
@gxy001
谢谢orz
by ningago @ 2022-06-07 18:06:12
@liqingyang
所以要卡起常来我是加还是不加呢
by Alex_Wei @ 2022-06-07 18:13:24
@ningago 不加的话时间复杂度没问题,但是递归深度没有严格
当需要用到点分树的性质来构造的时候必须规范写法,否则就寄了,举个例子:https://www.luogu.com.cn/problem/CF776F
by Alex_Wei @ 2022-06-07 18:14:12
至于常数的话,其实不好说,因为每次重新 dfs 求 size 也挺慢的。
by Alex_Wei @ 2022-06-07 18:14:51
(顺便提供一道水黑,大雾)
by ningago @ 2022-06-07 18:16:47
@Alex_Wei
thx orz