标签：子树 ThroughPath dfs 内点 出发 sim out

[ABC187E] Through Path

思路

我们考虑利用 dfs 序将树转换成一个序列（树链剖分中的一小部分），如下图所示：

图上的括号里有两个参数，第一个参数 \(in_u\) 就是所谓的 dfs 序，而后面的 \(out_u\) 则是这个点为根的子树中 dfs 序最大的点的 dfs 序。

这两个参数对应的就是以某个点为根的子树内的所有点，如 \((2,5)\) 即以 \(2\) 为根的子树（\(dfs_2=2,dfs_3=5,dfs_4=3,dfs_5=4\)）。

然后现在我们要进行操作，我们钦定 \((u,v)\) 边中，\(u\) 为 \(v\) 的父亲，然后我们考虑从 \(u\) 出发和从 \(v\) 出发。

1. 从 \(u\) 出发，那么除了 \(v\) 的子树内点无法到达，其余的所有点均可达，那么修改 \(1\sim in_v-1,out_v+1\sim n\)。
2. 从 \(v\) 出发，那么只有 \(v\) 的子树内点可达，修改 \(in_v\sim out_v\)。

可以发现查询是在操作做完之后，所以考虑做一遍序列上的差分即可。

代码

标签：子树,ThroughPath,dfs,内点,出发,sim,out
From： https://www.cnblogs.com/wscqwq/p/17598933.html