48分树剖求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    char ch=getchar();
    int s=0,w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return w*s;
}
int n,k;
int a[10000010];
struct node{
	int to,next;
}tu[10000010];
int cnt,head[10000010];
void add(int u,int v){
	tu[++cnt]={v,head[u]};
	head[u]=cnt;
}
int fa[10000010],deep[10000010],siz[10000010],son[10000010];
void dfs1(int p,int f,int dp){
	deep[p]=dp;
	fa[p]=f;
	siz[p]=1;
	int weison=-1;
	for(int i=head[p];i;i=tu[i].next){
		int v=tu[i].to;
		if(v==f) continue;
		dfs1(v,p,dp+1);
		siz[p]+=siz[v];
		if(siz[v]>weison){
			son[p]=v;weison=siz[v];
		}
	}
}
int dfn[10000010],ran[10000010],top[10000010];
int res;
void dfs2(int p,int tp){
	dfn[p]=++res;
	top[p]=p;
	if(!son[p]) return;
	dfs2(son[p],tp);
	for(int i=head[p];i;i=tu[i].next){
		int v=tu[i].to;
		if(v==fa[p] || v==son[p]) continue;
		dfs2(v,v);
	}
}
struct Tree{
	int l,r,sum;
}tree[10000010];
int tag[10000010];
void build(int p,int l,int r){
	tree[p]={l,r,0};
	if(l==r){
//		tree[p].sum=ran[r];
		return;	
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
//	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void push_dawn(int p){
	if(tag[p]){
		tag[p*2]+=tag[p];tag[p*2+1]+=tag[p];
		tree[p*2].sum+=tag[p];
		tree[p*2+1].sum+=tag[p];
		tag[p]=0;
	}
}
void update(int p,int d,int lef,int rig){
	if(tree[p].l>=lef && tree[p].r<=rig){
		tree[p].sum+=d;
		tag[p]+=d;
		return;
	}
	push_dawn(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(lef<=mid) update(p*2,d,lef,rig);
	if(rig>mid) update(p*2+1,d,lef,rig);
	tree[p].sum=max(tree[p*2].sum,tree[p*2+1].sum);
}
int query(int p,int lef,int rig){
	if(tree[p].l>=lef && tree[p].r<=rig){
//		cout<<tree[p].sum<<"___"<<endl;
		return tree[p].sum;
	}
	push_dawn(p);
	int mid=(tree[p].l+tree[p].r)/2;
	int ans=0;
	if(lef<=mid) ans=max(ans,query(p*2,lef,rig));
//	cout<<ans<<" ---"<<endl;
	if(rig>mid) ans=max(ans,query(p*2+1,lef,rig));
//	cout<<ans<<" ---"<<endl;
	return ans;
}
void updist(int x,int y,int d){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		update(1,d,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	update(1,d,dfn[x],dfn[y]);
}
signed main(){
//	freopen("P3128_2.in","r",stdin);
	n=read();k=read();
	for(int i=1,u,v;i<n;i++){
		u=read();v=read();
		add(u,v);add(v,u);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	int u,v;
	while(k--){
		u=read();v=read();
		updist(u,v,1);
	}
	printf("%lld\n",query(1,dfn[1],dfn[1]+siz[1]-1));
	return 0;
}