1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
int to,next;
}e[1000005];
struct tree
{
int L,R,maxx,addv;
}T[2000005];
int n,m,siz[500005],d[500005],h[500005],pre[500005],vson[500005],pos[500005],top[500005],sign,cnt;
inline void Addedge(int x,int y)
{
e[++cnt]=(Node){y,h[x]};h[x]=cnt;return;
}
inline void dfs1(int x,int dep)
{
int i,y;
d[x]=dep;siz[x]=1;
vson[x]=-1;
for(i=h[x];i;i=e[i].next)
{
y=e[i].to;
if(y==pre[x])continue;
pre[y]=x;
dfs1(y,dep+1);
siz[x]+=siz[y];
if(vson[x]==-1||siz[vson[x]]<siz[y])vson[x]=y;
}
return;
}
inline void dfs2(int x,int sp)
{
int i,y;
pos[x]=++sign;top[x]=sp;
if(vson[x]!=-1)dfs2(vson[x],sp);
for(i=h[x];i;i=e[i].next)
{
y=e[i].to;
if(y==pre[x]||y==vson[x])continue;
dfs2(y,y);
}
return;
}
inline void Build(int L,int R,int v)
{
T[v].L=L;T[v].R=R;
if(L==R)return;
int mid=(L+R)>>1;
Build(L,mid,v<<1);
Build(mid+1,R,(v<<1)|1);
return;
}
inline void pushup(int v)
{
T[v].maxx=max(T[v<<1].maxx,T[(v<<1)|1].maxx)+T[v].addv;
return;
}
inline void Insert(int L,int R,int v)
{
if(L>T[v].R||R<T[v].L)return;
if(L<=T[v].L&&R>=T[v].R)
{
++T[v].addv;++T[v].maxx;
return;
}
Insert(L,R,v<<1);
Insert(L,R,(v<<1)|1);
pushup(v);
return;
}
inline void Insertpath(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])swap(x,y);
Insert(pos[top[x]],pos[x],1);
x=pre[top[x]];
}
if(d[x]>d[y])swap(x,y);
Insert(pos[x],pos[y],1);
return;
}
int main(void)
{
int i,n,m,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
Addedge(x,y);
Addedge(y,x);
}
dfs1(1,1);
dfs2(1,1);
Build(1,sign,1);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
Insertpath(x,y);
}
printf("%d\n",T[1].maxx);
return 0;
}
|