# Paths on the tree

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 80 Accepted Submission(s): 25

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

Author

Xiaoxu Guo (ftiasch)

Source

2014 Multi-University Training Contest 5

随便选择一个根。变成有根树。


### 然后每个路径，u - v 找出u - v的LCA。

/* ***
Author :kuangbin
Created Time :2014/8/5 19:37:30
File Name :E:\2014ACM\比赛\2014多校训练\2014多校5\HDU4912.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
const int DEG = 20;
struct Edge
{
int to,next;
}edge[MAXN*2];
void init()
{
tot = 0;
}
{
edge[tot].to = v;
}
int fa[MAXN][DEG];
int deg[MAXN];
void BFS(int root)
{
queueq;
deg[root] = 0;
fa[root][0] = root;
q.push(root);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 1;i < DEG;i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(v == fa[u][0])continue;
deg[v] = deg[u] + 1;
fa[v][0] = u;
q.push(v);
}
}
}
int LCA(int u,int v)
{
if(deg[u] > deg[v])swap(u,v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for(int det = hv-hu,i=0;det;det>>=1,i++)
if(det&1)
tv = fa[tv][i];
if(tu == tv)return tu;
for(int i = DEG-1;i >= 0;i–)
{
if(fa[tu][i] == fa[tv][i])continue;
tu = fa[tu][i];
tv = fa[tv][i];
}
return fa[tu][0];
}
bool vis[MAXN];
void gao(int u)
{
if(vis[u])return;
vis[u] = true;
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(v == fa[u][0])continue;
gao(v);
}
}
struct Node
{
int u,v;
int lca;
}node[MAXN];
bool cmp(Node a,Node b)
{
return deg[a.lca] > deg[b.lca];
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m;
while(scanf(“%d%d”,&n,&m) == 2)
{
init();
int u,v;
for(int i = 1;i < n;i++)
{
scanf(“%d%d”,&u,&v);
}
BFS(1);
for(int i = 0;i < m;i++)
{
scanf(“%d%d”,&node[i].u,&node[i].v);
if(deg[node[i].u] > deg[node[i].v])
swap(node[i].u,node[i].v);
node[i].lca = LCA(node[i].u,node[i].v);
}
sort(node,node+m,cmp);
int ans = 0;
memset(vis,false,sizeof(vis));
for(int i = 0;i < m;i++)
{
if(vis[node[i].u] || vis[node[i].v])continue;
ans++;
gao(node[i].lca);
}
printf(“%d\n”,ans);
}
return 0;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 333.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%