solution-code4837

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