hdu 4912

Paths on the tree
Problem Description
bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.**

There are m paths on the tree. bobo would like to pick some paths while any two paths do not share common vertices.**

Find the maximum number of paths bobo can pick.**

Input
The input consists of several tests. For each tests:**

The first line contains n,m (1≤n,m≤105). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following m lines contain 2 integers ui,vi denoting a path between vertices ui and vi (1≤ui,vi≤n).**

Output
For each tests:

A single integer, the maximum number of paths.**

Sample Input
3 2
1 2
1 3
1 2
1 3
7 3
1 2
1 3
2 4
2 5
3 6
3 7
2 3
4 5
6 7

Sample Output
1
2

析：n个点的树中有两个点构成的m条路，求每一条路都不包含公共点或边的情况下最多的路的条数，用LCA倍增算法，求出每条路的两个点的LCA，并对其LCA按深度从大到小排序，先取深度较大的边，这样并不会对浅边产生影响，但要维护其LCA下的所有子节点，对其进行标记，避免重复

#include <vector>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define ll long long
#define ull unsigned ll
#define Inf 0x7fffffff
#define maxn 100005
#define maxm 100005
#define P pair<int, int>
using namespace std;
const int N = 300005;
int t, n, m, len, ans;
int vis[maxn], deep[maxn];
int x, y, mark[maxn], f[maxn][30];
vector<int>V[maxn];
struct Node{
    int x, y, p;
    bool operator<(const Node &a)const{
        return deep[p] > deep[a.p];
    }
}g[maxn];
void init(){
    for(int i = 1; i <= n; i ++){
        vis[i] = deep[i] = mark[i] = 0;
        fill(f[i], f[i]+30, 0);
        V[i].clear();
    }
}
void dfs(int u){
    vis[u] = 0;
    for(int i = 0; i < V[u].size(); i ++){
        int v = V[u][i];
        if(f[u][0] == v)
            continue;
        if(!vis[v]){
            deep[v] = deep[u]+1;
            f[v][0] = u;
            dfs(v);
        }
    }
}
void cal(){
    for(int i = 1; (1<<i) <= n; i ++){
        for(int j = 1; j <= n; j ++){
            f[j][i] = f[f[j][i-1]][i-1];
        }
    }
}
int LCA(int x, int y){
    if(deep[x] < deep[y])
        swap(x, y);
    int j, i = 0;
    while((1<<(i+1)) <= deep[x])
        i ++;
    for(j = i; j+1; j --){
        if(deep[x]-(1<<j) >= deep[y]){
            x = f[x][j];
        }
    }
    if(x == y) return x;
    for(j = i; j+1; j --){
        if(f[x][j] != f[y][j]){
            x = f[x][j];
            y = f[y][j];
        }
    }
    return f[x][0];
}
void solve(int u){
    mark[u] = 1;
    for(int i = 0; i < V[u].size(); i ++){
        int v = V[u][i];
        if(deep[u]+1 == deep[v] && !mark[v]){
            solve(v);
        }
    }
}
int main(){
    while(~scanf("%d%d", &n, &m)){
        init();
        for(int i = 1; i < n; i ++){
            scanf("%d%d", &x, &y);
            V[x].push_back(y);
            V[y].push_back(x);
        }
        deep[1] = f[1][0] = 1;
        dfs(1), cal();
        for(int i = 0; i < m; i ++){
            scanf("%d%d", &g[i].x, &g[i].y);
            g[i].p = LCA(g[i].x, g[i].y);
        }
        int res = 0;
        sort(g, g+m);
        for(int i = 0; i < m; i ++){
            if(!mark[g[i].x] && !mark[g[i].y]){
                res ++;
                solve(g[i].p);
            }
        }
        printf("%d
", res);
    }
    return 0;
}