题目链接

https://www.luogu.com.cn/problem/P3128

解题思路

树上差分
LCA
知道树上差分在什么情况下使用，树上路径，树上两点等。

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10;
const int INF=0x3f3f3f3f;

vector<int> e[N];
int n,k,a,b,ans=-INF,Time;
int sum[N],path[N<<1],st[N<<1][20],pos[N<<1][20],dp[N],in[N],fa[N],d[N];

void dfs(int x,int father,int deep)
{
    path[++Time]=x;
    fa[x]=father;
    if(dp[x]==0) dp[x]=deep;
    if(in[x]==0) in[x]=Time;
    for(int i=0;i<e[x].size();i++)
    {
        if(father==e[x][i])  continue;
        dfs(e[x][i],x,deep+1);
        path[++Time]=x;
    }
}

void ST()//建立ST表
{
    for(int i=1;i<=Time;i++) st[i][0]=dp[path[i]],pos[i][0]=i;

    for(int j=1;(1<<j)<=Time;j++)
    for(int i=1;i+(1<<j-1)-1<=Time;i++)
    if(st[i][j-1]<st[i+(1<<j-1)][j-1]) 
    st[i][j]=st[i][j-1],pos[i][j]=pos[i][j-1];
    else 
    st[i][j]=st[i+(1<<j-1)][j-1],pos[i][j]=pos[i+(1<<j-1)][j-1];
}

int LCA(int x,int y)//求最近公共祖先
{
    int tx=in[x],ty=in[y];
    if(tx>ty) swap(tx,ty);
    int k=0;while(tx+(1<<k+1)-1<=ty) k++;
    return st[tx][k]<st[ty-(1<<k)+1][k]?path[pos[tx][k]]:path[pos[ty-(1<<k)+1][k]];
}

int dfss(int x,int fa)//递归求和，确定每个节点的值
{
    if(sum[x]!=INF) return sum[x];
    sum[x]=d[x];
    for(int i=0;i<e[x].size();i++)
    {
        if(fa==e[x][i]) continue;
        sum[x]+=dfss(e[x][i],x);    
    }
    ans=max(sum[x],ans);
    return sum[x];
}

int main()
{
    memset(sum,0x3f,sizeof sum);

    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    dfs(1,0,1);
    ST();

    while(k--)
    {
        cin>>a>>b;
        int c=LCA(a,b);
        d[a]++; d[b]++; d[c]--; d[fa[c]]--;
    }

    dfss(1,0);//假设1号节点为根
    cout<<ans<<endl;

    return 0;
}