调吐了已经 求助大佬
by zzxLLL @ 2021-08-28 23:40:12
DFS2 不先搜重儿子吗?还是写法不同?
by xfrvq @ 2021-08-29 00:02:11
@[zzx23362838](/user/469066)
by xfrvq @ 2021-08-29 00:06:01
写法不一样 应该是对的 这样写LCA过了
by zzxLLL @ 2021-08-29 09:18:13
dfs2改成了:
```cpp
int top[M],id[M],rev[M],cnt;
void dfs2(int u,int topf){
id[u]=++cnt;
rev[cnt]=u;
top[u]=topf;
if(son[u]==0) return;
dfs2(son[u],topf);
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
```
还是全wa
by zzxLLL @ 2021-08-29 09:29:27
@[zzx23362838](/user/469066) 建议开 long long,不然更新区间和时会爆、
by kouylty @ 2021-08-29 09:30:45
@[kouylan](/user/123298) 改了 还是全wa
by zzxLLL @ 2021-08-29 12:22:37
@[zzx23362838](/user/469066) build 函数里应该是 ```tree[k].val = w[rev[l]];```
因为线段树下标是 dfs 序。
by kouylty @ 2021-08-29 13:01:13
@[kouylan](/user/123298) 感谢大佬 已经ac了 orz
by zzxLLL @ 2021-08-29 13:30:19