转自http://blog.csdn.net/Fine_rose/article/details/77991839
已知路径求被所有路径覆盖的边
- 首先对已知的这 n 条路径的 起点a 和 终点b 的权值 +1 ，并对 lca(a, b) 的权值 -2 。
- 从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值。
- 那么满足要求的边就是 权值等于n的节点 与其 父节点 所连的边
dfs代码(使用前向星存图):
void dfs(int x, int father) { // x 为深搜的节点, father 为 x 节点的父节点
int to;
for (int i = head[x]; i; i = edges[i].next) {
to = edges[i].to; // 枚举由 x 节点能够到达的所有的节点
if (to != father) { // 筛掉 x 节点的父节点
dfs(to, x); // 深搜 to 节点， 并设置其父节点为x
value[x] += value[to]; // 累加权值和
}
}
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
已知路径求树上所有节点被路径覆盖次数
- 对每条路径的 起点a和终点b 的权值 +1 , 对 lca(a, b) 的权值 -1 , 对 lca(a, b)的父节点 权值 -1
- 从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值
- 每个节点的权值既是其被路径覆盖的次数
