HDU 4912

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。

根据所有路径的LCA的深度进行选择。每选择一个路径以后，把LCA下面的子树都进行标记。如果u,v没有被标记，这个路径是可以的。贪心的正确性很容易想明白。

/* ***
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 <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];
int head[MAXN],tot;
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
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);
addedge(u,v);
addedge(v,u);
}
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;
}