标签：遍历 ++ tot id dfs LCA 莫队虚树

括号序

进加一次，出加一次，显然最后得到的序列只有 \(2n\) 个点。

void dfs(int x) {
	in[x]=++tot;
	for(y) dfs(y);
	out[x]=++tot;
}

显然我们希求将树上路径表示为区间，然后用莫队抑或是其它数据结构维护。

对于 \(y\in T_x\) 的情况就是上图，我们发现只要取 \([in_x,in_y]\) 即可达到只有路径上的点被加了一次，其他要么没加要么加 \(2\) 次。因此，我们只保留加 \(1\) 次的点。也就是说每次更新一个点就取反它的是否加入状态。

否则，显然我们取 \([out_x,in_y]\)，再补上 \(LCA\) 的贡献即可。

用来求 LCA 以及求的方式能够证明某些结论。

void dfs(int x) {
	id[x]=++tot; v[tot]=x;
	for(y) {
		dfs(y);
		v[++tot]=x;
	}
}

我们可以猜想 \(x,y\) 的 LCA 就是 \(v[id_x,id_y]\) 深度最浅的点。

下文假定 \(id_x<id_y\)/

不难发现命题等价于记 \(LCA(x,y)=d\)，\(d\) 的祖先不在区间内，\(d\) 的兄弟不在区间内，\(d\) 出现在区间内。

考虑 \(id_{fa_d}<id_x<id_y\) ，且要再次出现 \(fa_d\) 要等到 \(d\) 回溯完后才出现。所以一定不会出现。

考虑在 \(d\) 之前遍历的兄弟无影响（因为要之前的遍历完才可能遍历到 \(d\)），之后的不会在区间取到，因为要 \(d\) 回溯上去再遍历兄弟，所以兄弟不在区间内。

若 \(d=x\)，显然正确。因为显然 \([id_x,id_y]\) 都在 \(x\) 子树内。最浅的一定是 \(x\)。

若不是，则 \(x,y\) 分居 \(d\) 的不同子树，那么要实现不同子树的遍历一定需要回溯到 \(d\) 再遍历下去，所以一定存在 \(d\)。

综上，这样是对滴。

标签：遍历,++,tot,id,dfs,LCA,莫队,虚树
From： https://www.cnblogs.com/xugangfan/p/16583732.html

dfs序括号序欧拉序树上莫队虚树建立傻傻分不清