题解——暗的连锁（树上差分）

这道题真的很巧妙，如果不看题解，就ssw02的智商，是完全想不到的

题目搬运： POJ3417

Dark 是一张无向图，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 N–1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 M条附加边。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

输入格式
第一行包含两个整数 N 和 M；
之后 N–1 行，每行包括两个整数 A 和 B表示 A 和 B 之间有一条主要边；
之后 M 行以同样的格式给出附加边。

输出格式
输出一个整数表示答案。

解题思路

性质的分析：

1.主要边的集合构成了一棵树（显然），而附加边就是图上的非树边。

2.先割掉主要边和先割掉附加边是等效的。

3.附加边与主要边会共同组成环的结构。

合法情况：

满足下面两个条件：

1.由于环的存在，每次切掉一条附加边（X,Y），那么主要边上节点X到节点Y中必须被切掉一条边。

2.这条主要边不会同时在2个及以上的环中出现（即不是环的交叉部分）

简化抽象问题：

我们可以将原题抽象成以下覆盖问题：（本段参考一本通提高篇）

给定一个无向图和一颗生成树，求每条树边被非树边覆盖了几次（附加边(X,Y)将X，Y间的主要边路径覆盖一次）。

问题解决：

一个典型的树上区间的修改，我们可以考虑用——>树上差分。（逃避树链剖分）

本题中具体而言，建立出主要边形成的树，就是对于每一条附加边（X，Y）,将 X , Y 的权值+1 , LCA 的权值 -2 。（初值都为0）。

然后，然后，没有然后，跑DFS求出子树权值和f[]就行了。f[ X ]表示 X 和 father[ X ]所连的边被覆盖了多少次。

统计答案：如果f[x]>=2 ,无论如何切都不行（环的交集），f[x]=1 对答案贡献+1 , ,f[x]=0 ，任意切一条即可 ,贡献为 M

由于ssw02懒得找图，想不明白就自己画画就出来了

AC code:

#include <bits/stdc++.h>//为什么从LOJ拷贝下来码风就变了？？
using namespace std;
const int MAXN = 100005;
int N, M, head[MAXN], to[MAXN * 2], nex[MAXN * 2], tot = 1;
int anc[MAXN][20], f[MAXN], dep[MAXN], val[MAXN], ans = 0;
inline int read() {
    int s = 0;
    char g = getchar();
    while (g > '9' || g < '0') g = getchar();
    while (g >= '0' && g <= '9') s = s * 10 + g - '0', g = getchar();
    return s;
}
void add(int x, int y) { to[++tot] = y, nex[tot] = head[x], head[x] = tot; }
void dfs(int u, int fa) { // 跑深度，用于求 LCA
    anc[u][0] = fa;
    for (register int i = 1; i <= 17; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (register int i = head[u]; i; i = nex[i]) {
        if (to[i] == fa)
            continue;
        dep[to[i]] = dep[u] + 1;
        dfs(to[i], u);
    }
}
void dfs2(int u, int fa) { // 求f[]数组+统计答案
    f[u] = val[u];
    for (register int i = head[u]; i; i = nex[i]) {
        if (to[i] == fa)
            continue;
        dfs2(to[i], u);
        f[u] += f[to[i]];
    }//如果f[x]>=2 ,无论如何切都不行（环的交集） ，f[x]=1 对答案贡献+1 , ,f[x]=0 ，任意切一条即可 ,贡献为 M
    if (f[u] == 1 && u != 1)
        ans++;
    if (f[u] == 0 && u != 1)
        ans += M;
}
int lca(int x, int y) {
    if (dep[y] > dep[x])
        swap(x, y);
    int t = dep[x] - dep[y];
    for (register int p = 0; t; t >>= 1, ++p)
        if (t & 1)
            x = anc[x][p];
    if (x == y)
        return x;
    for (register int p = 17; anc[x][0] != anc[y][0]; p--)
        if (anc[x][p] != anc[y][p])
            x = anc[x][p], y = anc[y][p];
    return anc[x][0];
}
int main() {
    N = read(), M = read();
    int m1, m2;
    for (register int i = 1; i < N; ++i) {
        m1 = read(), m2 = read();
        add(m1, m2), add(m2, m1);
    }
    dfs(1, 1);
    for (register int i = 1; i <= M; ++i) {
        m1 = read(), m2 = read();
        val[m1] += 1, val[m2] += 1, val[lca(m1, m2)] -= 2;
    }
    dfs2(1, 1);
    cout << ans;
}
// 4 1 1 2 2 3 1 4 3 4