题目链接：hdu 4912 Paths on the tree

题目大意：给定一棵树，和若干个通道。要求尽量选出多的通道，而且两两通道不想交。

解题思路：用树链剖分求LCA，然后依据通道两端节点的LCA深度排序，从深度最大优先选。推断两个节点均没被标

记即为可选通道。

每次选完通道。将该通道LCA下面点所有标记。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int N, M, E, first[maxn], jump[maxn * 2], link[maxn * 2], vis[maxn];

int id, idx[maxn], top[maxn], far[maxn], son[maxn], cnt[maxn], dep[maxn];

inline void add_Edge (int u, int v) {

    link[E] = v;

    jump[E] = first[u];

    first[u] = E++;

}

void dfs (int u, int pre, int d) {

    far[u] = pre;

    son[u] = 0;

    cnt[u] = 1;

    dep[u] = d;

    for (int i = first[u]; i + 1; i = jump[i]) {

        int v = link[i];

        if (v == pre)

            continue;

        dfs(v, u, d + 1);

        cnt[u] += cnt[v];

        if (cnt[son[u]] < cnt[v])

            son[u] = v;

    }

}

void dfs (int u, int rot) {

    top[u] = rot;

    idx[u] = ++id;

    if (son[u])

        dfs(son[u], rot);

    for (int i = first[u]; i + 1; i = jump[i]) {

        int v = link[i];

        if (v == far[u] || v == son[u])

            continue;

        dfs(v, v);

    }

}

void dfs (int u) {

    if (vis[u])

        return;

    vis[u] = 1;

    for (int i = first[u]; i + 1; i = jump[i]) {

        int v = link[i];

        if (v == far[u])

            continue;

        dfs(v);

    }

}

struct query {

    int u, v, r, d;

    void set(int u, int v, int r, int d) {

        this->u = u;

        this->v = v;

        this->r = r;

        this->d = d;

    }

    friend bool operator < (const query& a, const query& b) {

        return a.d > b.d;

    }

}q[maxn];

int LCA (int u, int v) {

    int p = top[u], q = top[v];

    while (p != q) {

        if (dep[p] < dep[q]) {

            swap(p, q);

            swap(u, v);

        }

        u = far[p];

        p = top[u];

    }

    return dep[u] < dep[v] ? u : v;

}

void init () {

    E = id = 0;

    memset(first, -1, sizeof(first));

    int u, v;

    for (int i = 1; i < N; i++) {

        scanf("%d%d", &u, &v);

        add_Edge(u, v);

        add_Edge(v, u);

    }

    dfs(1, 0, 0);

    dfs(1, 1);

    for (int i = 0; i < M; i++) {

        scanf("%d%d", &u, &v);

        int rot = LCA(u, v);

        q[i].set(u, v, rot, dep[rot]);

    }

    sort(q, q + M);

}

int main () {

    while (scanf("%d%d", &N, &M) == 2) {

        init();

        int ans = 0;

        memset(vis, 0, sizeof(vis));

        for (int i = 0; i < M; i++) {

            if (vis[q[i].u] || vis[q[i].v])

                continue;

            dfs(q[i].r);

            ans++;

        }

        printf("%d\n", ans);

    }

    return 0;

}