如题，人没了

伸手

P3128

思路是树剖映射数组，差分实现区间加，最后O(n)取答案

上码

#include <bits/stdc++.h>
using namespace std;
int n,k;
struct Node
{
    int dep;
    int st;
    int hson;
    int top;
    int size;
    int fat;
    int dfn;
}node[50001];
struct Edge
{
    int des;
    int next;
}edge[100001];
int cnt;
int cnl;
inline void add(int a,int b)
{
    cnt++;
    edge[cnt].des=b;
    edge[cnt].next=node[a].st;
    node[a].st=cnt;
    return;
}
void dfs1(int poi,int upon,int depth)
{
    int vll=0;
    node[poi].size=1;
    node[poi].fat=upon;
    node[poi].dep=depth;
    for(int i=node[poi].st;i!=0;i=edge[i].next)
    {
        int flag=edge[i].des;
        if(flag!=upon)
        {
            dfs1(flag,poi,depth+1);
            node[poi].size+=node[flag].size;
            if(node[flag].size>vll)
            {
                vll=node[flag].size;
                node[poi].hson=flag;
            }
        }
    }
    return;
}
void dfs2(int poi)
{
    if(node[node[poi].fat].hson!=poi)
    {
        node[poi].top=poi;
    }
    else
    {
        node[poi].top=node[node[poi].fat].top;
    }

    cnl++;
    node[poi].dfn=cnl;

    if(node[poi].hson!=0)
    {
        dfs2(node[poi].hson);
        for(int i=node[poi].st;i!=0;i=edge[i].next)
        {
            int flag=edge[i].des;
            if(flag!=node[poi].hson&&flag!=node[poi].fat)
            {
                dfs2(flag);
            }
        }
    }

    return;
}
int tee[50001];
void Insert(int s,int r)
{
    bool flag=0;
	while(node[s].top!=node[r].top)
    {
        if(node[s].dep>=node[r].dep)
        {
            tee[node[node[s].top].dfn]++;
            tee[node[s].dfn+1]--;
            if(node[s].top==1)
        	{
        		flag=1;
        	}
            s=node[node[s].top].fat;
        }
        else
        {
            tee[node[node[r].top].dfn]++;
            tee[node[r].dfn+1]--;
            if(node[r].top==1)
        	{
        		flag=1;
        	}
            r=node[node[r].top].fat;
        }
    }
    if(s!=r)
    {
        if(node[s].dep>node[r].dep)
        {
            if(flag==1)
            {
            	tee[2]++;
            }
			else
			{
				tee[node[r].dfn]++;
			}
            tee[node[s].dfn+1]--;
        }
        else
        {
            if(flag==1)
            {
            	tee[2]++;
            }
			else
			{
				tee[node[s].dfn]++;
			}
            tee[node[r].dfn+1]--;
        }
    }
    else
    {
        if(flag==1)
        {
        	return;
        }
		tee[node[s].dfn]++;
        tee[node[s].dfn+1]--;
    }
    return;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }

    dfs1(1,1,1);//
    dfs2(1);
    node[0].top=1;

    for(int i=1;i<=k;i++)
    {
        int s,t;
        scanf("%d %d",&s,&t);
        Insert(s,t);
    }

    int maxn=-1e9;
    for(int i=1;i<=n;i++)
    {
        tee[i]+=tee[i-1];
        maxn=max(maxn,tee[i]);
    }

    printf("%d\n",maxn);
    // system("pause");
    return 0;
}
/*
7 5
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
2 6
2 7
1 3
*/