@[HybridTheory](/user/41485) @[Binary_Search_Tree](/user/40985)
by Miku_shadow @ 2019-11-16 16:49:55
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=1000005;
struct node
{
int next;
int to;
}edge[Maxn];
int head[Maxn],a[Maxn],cnt,ans=0;
int dis[Maxn][22],deep[Maxn];
void add(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
void DFS(int u,int fa)
{
deep[u]=deep[fa]+1;
dis[u][0]=fa;
for(int i=1;i<=20;i++)
{
dis[u][i]=dis[dis[u][i-1]][i-1];
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v!=fa)
{
DFS(v,u);
}
}
return ;
}
int LCA(int x,int y)
{
if(deep[x]<deep[y])
{
swap(x,y);
}
for(int i=20;i>=0;i--)
{
if((1<<i)<=deep[x]-deep[y])
{
x=dis[x][i];
}
}
if(x==y)return x;
for(int i=20;i>=0;i--)
{
if(dis[x][i]!=dis[y][i])
{
x=dis[x][i];
y=dis[y][i];
}
}
return dis[x][0];
}
void calc(int u,int fa)
{
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v!=fa)
{
calc(v,u);//qwq
a[u]=a[u]+a[v];
}
}
ans=max(ans,a[u]);
return ;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
DFS(1,0);
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=LCA(x,y);
//cout<<lca<<endl;
a[x]++;
a[y]++;
a[lca]--;
a[dis[lca][0]]--;
}
calc(1,0);
cout<<ans<<endl;
return 0;
}
```
by LivingThings @ 2019-11-16 16:55:12
@[Miku_shadow](/user/218412) 今天考了2道树论了,你觉得明天还会考???
by 追风少年σχ @ 2019-11-16 16:56:12
@[LinkinPark](/user/78203) 啊,我又智障了,估计早上T2也这么挂的。。。。
by Miku_shadow @ 2019-11-16 16:56:47
@[追风少年σχ](/user/31621) 反正我废了,day1 50分都没有,我晚上颓废了没希望了
by Miku_shadow @ 2019-11-16 16:58:34