「poj 3417」Network (树上差分)

poj 3417
题意：一棵有$N$个点的树，再往里面加入$M$条新边，现在要破坏其中的两条边，要求一条是原来树中的边，一条是新边，然后使图不连通，求方案的数量。
发现加的新边会使树产生环。观察可得一条新边$(x,y)$如果在树上$(u,v)$路径都加一，那么最后如果想使图不连通，则只能删边权为0,1的点，对于边权为0的边能删$m$次，而边权为1的边只能删1次。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 200000 + 5, LOGS = 20;

    struct edge {
        int v, nxt;
    } ed[MAXN * 2];

    int n, m, cf[MAXN], pre[MAXN][LOGS + 5], dep[MAXN], en, hd[MAXN];

    void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}

    void dfs(int u, int fa) {
        dep[u] = dep[fa] + 1, pre[u][0] = fa;
        for (int i = 1; i <= LOGS; ++i) pre[u][i] = pre[pre[u][i - 1]][i - 1];
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) dfs(e.v, u);
        }
    }
    int LCA(int a, int b) {
        if (dep[a] < dep[b]) swap(a, b);
        for (int i = LOGS; i >= 0; --i) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
        if (a == b) return a;
        for (int i = LOGS; i >= 0; --i) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
        return pre[a][0];
    }
    int ans = 0ll;
    void dfs2(int u, int fa) {
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) dfs2(e.v, u), cf[u] += cf[e.v];
        }
        if (fa != 0) {
            if (cf[u] == 0) ans += m; 
            if (cf[u] == 1) ++ans;
        }
    }

    void clean() {
        en = 0, ms(hd, -1), ms(dep, 0), ms(cf, 0);
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &m);
        for (int x, y, i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            ins(x, y), ins(y, x);
        }
        dfs(1, 0);
        for (int x, y, i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            if (x == y) continue ; // 注意重边
            cf[LCA(x, y)] -= 2, ++cf[x], ++cf[y];
        }
        dfs2(1, 0);
        printf("%d\n", ans);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}