P3128 [USACO15DEC]最大流Max Flow（树上点查分）

题目链接：https://www.luogu.org/problemnew/show/P3128

树上差分，顾名思义就是在树上搞差分。有两种典型题型，一种是边差分，一种是点差分。

边差分裸题长这样：
给你一棵树，有n次修改操作，每次把u..v的路径权值加x，最后问从x..y的路径权值和。

点差分和边差分稍有差别：
有n次修改操作，每次把u..v的所有点权都加x，最后问点权最大的为多少。

本题为点拆分的模板题，通过在两个端点处+1，并在lca和lca的父节点分别减一后遍历全树实现

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int head[100010];
int cnt,n,k;
struct node
{
    int v,next;
}edge[200020];
int fa[200010][22],lg[500050],power[100010],deep[100010];
int ans;
void add(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs(int f,int fath)
{
    deep[f]=deep[fath]+1;
    fa[f][0]=fath;
    for(int i=1;(1<<i)<=deep[f];i++)
    {
        fa[f][i]=fa[fa[f][i-1]][i-1];
    }
    for(int i=head[f];i!=-1;i=edge[i].next)
    {
        if(edge[i].v!=fath)
            dfs(edge[i].v,f);
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y])
    {
        swap(x,y);
    }
    while(deep[x]>deep[y])
    {
        x=fa[x][lg[deep[x]-deep[y]]-1];
    }
    if(x==y)
        return x;
    for(int k=lg[deep[x]];k>=0;k--)
    {
        if(fa[x][k]!=fa[y][k])
        {
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}

void get(int cur,int fa)
{
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        if(edge[i].v==fa)continue;
        get(edge[i].v,cur);
        power[cur]+=power[edge[i].v];
    }
    ans=max(ans,power[cur]);
}

int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cnt=0;
    ans=0;
    int lca_node;
    cin>>n>>k;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    deep[0]=0;
    dfs(1,0);
    while(k--)
    {
        cin>>u>>v;
        lca_node=lca(u,v);
        power[u]++;
        power[v]++;
        power[lca_node]--;
        power[fa[lca_node][0]]--;
    }
    get(1,0);
    cout<<ans<<endl;
    return 0;
}