POJ3417 Network暗的连锁 （树上差分）

树上的边差分，x++，y++，lca(x,y)-=2.

m条边可以看做将树上的一部分边覆盖，就用差分，x=1，表示x与fa(x)之间的边被覆盖一次，m次处理后跑一遍dfs统计子树和，每个节点子树和val=1，说明割去这条边后只有一种方案，val=0，说明割去后随便再割一条都行，有m中方案。

题很简单但是调了半天，发现倍增的数组开小了（开的20），以后防止这种情况开成25应该比较稳妥。

 1 #include <cstdio>

 2 #include <iostream>

 3 #include <cstring>

 4 #include <cstdlib>

 5 #include <algorithm>

 6 #define ll long long

 7 using namespace std;

 8 const int N = 1e5 + 10;

 9 int head[N], to[N << 1], nxt[N << 1], tot;

10 void add(int x, int y) {

11     nxt[++tot] = head[x];

12     head[x] = tot;

13     to[tot] = y;

14 }

15 int n, m, d[N], f[N][21], val[N];

16 ll ans = 0;

17

18 void dfs(int u, int fa) {

19     for (int i = head[u]; i; i = nxt[i]) {

20         int v = to[i];

21         if (v == fa) continue;

22         d[v] = d[u] + 1;

23         f[v][0] = u;

24         for (int j = 1; j <= 20; j++)

25             f[v][j] = f[f[v][j - 1]][j - 1];

26         dfs(v,u);

27     }

28 }

29

30 int lca(int x, int y) {

31     if (d[x] > d[y]) swap(x, y);

32     for (int i = 20; i >= 0; i--)

33         if (d[f[y][i]] >= d[x]) y = f[y][i];

34     if (x == y) return x;

35     for (int i = 20; i >= 0; i--)

36         if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];

37     return f[x][0];

38 }

39

40 void solve(int u) {

41     for (int i = head[u]; i; i = nxt[i]) {

42         int v = to[i];

43         if (d[v] <= d[u]) continue;

44         solve(v);

45         val[u] += val[v];

46     }

47 }

48

49 int main() {

50     scanf("%d%d", &n, &m);

51     for (int i = 1; i < n; i++) {

52         int a, b;

53         scanf("%d%d", &a, &b);

54         add(a, b), add(b, a);

55     }

56     d[1] = 1, dfs(1,0);

57     for (int i = 1; i <= m; i++) {

58         int x, y; cin >> x >> y;

59         int z = lca(x, y);

60         val[x]++, val[y]++, val[z] -= 2;

61     }

62     solve(1);

63     for (int i = 2;i <= n; i++) {//注意从2开始，val[2]表示2和1之间这条边被覆盖的次数

64         if (val[i] == 0) ans += m;

65         if (val[i] == 1) ans ++;

66     }

67     printf("%lld\n", ans);

68     return 0;

69 }

POJ3417 Network暗的连锁 （树上差分）的相关教程结束。