题解——洛谷P3128 [USACO15DEC]最大流Max Flow

裸的树上差分

因为要求点权所以在点上差分即可

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int MAXlog = ;

int cnt=,u[MAXN*],v[MAXN*],first[MAXN],next[MAXN*];

int cf[MAXN];

int dep[MAXN],jump[MAXN][MAXlog+];

int n,k;

void addedge(int ux,int vx){

    cnt++;

    u[cnt]=ux;

    v[cnt]=vx;

    next[cnt]=first[ux];

    first[ux]=cnt;

}

void dfs(int u,int f){

    dep[u]=dep[f]+;

    jump[u][]=f;

    for(int i=;i<=MAXlog;i++)

        jump[u][i]=jump[jump[u][i-]][i-];

    for(int i=first[u];i;i=next[i])

        if(v[i]!=f)

            dfs(v[i],u);

}

int lca(int x,int y){

    if(dep[x]<dep[y])

        swap(x,y);

    for(int i=MAXlog;i>=;i--)

        if(dep[x]-(<<i)>=dep[y])

            x=jump[x][i];

    if(x==y)

        return x;

    for(int i=MAXlog;i>=;i--)

        if(jump[x][i]!=jump[y][i]){

            x=jump[x][i];

            y=jump[y][i];

        }

    return jump[x][];

}

int ans=;

void dfs2(int u,int f){

    for(int i=first[u];i;i=next[i]){

        if(v[i]==f)

            continue;

        dfs2(v[i],u);

        cf[u]+=cf[v[i]];

    }

    if(cf[u]>ans)

        ans=cf[u];

}

int main(){

    scanf("%d %d",&n,&k);

    for(int i=;i<=n-;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    dfs(,);

    for(int i=;i<=k;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        cf[a]++;

        cf[b]++;

        int l=lca(a,b);

        cf[l]-=;

        cf[jump[l][]]-=;

    }

    dfs2(,);

    printf("%d",ans);

    return ;

}