题目链接：P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

读题注意

从隔间s运输到隔间t，和从隔间t运输到隔间s，都没区别，因为加的压力是一样的，所以这是一个无向图。

并且只有N个节点和N-1条边，所以是一棵树。

分析

如果每次都去遍历[s,t]这个区间去给每个节点都加上1，那么复杂度肯定会T飞出去，因为是区间修改考虑用差分维护，但是这个是树，改变思路可以将节点s压力+1，节点t压力+1，lca(s,t)压力-2。

发现直接对lca减二并不符合运输情况，考虑递归回溯性质改成lca(s,t)压力-1，lca(s,t)父节点压力-1。

这样一边回溯一边累计答案就可以了。

AC代码（倍增LCA）

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;

int n,k,p[N],ans=INT_MIN,d[N];
int f[N][20],lg[N];
vector<int>e[N];
bitset<N>vis;
inline int read(){
    int x=0;char c=getchar();
    while(c<48 or c>57)c=getchar();
    while(c>=48 and c<=57)x=(x<<3)+(x<<1)+(c xor 48),c=getchar();
    return x;
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=f[x][lg[d[x]-d[y]]-1];
    if(x==y)return x;
    for(int i=lg[d[x]];i>=0;--i)
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
void dfs(int now,int fa){
    if(vis[now])return;
    vis[now]=true;
    d[now]=d[fa]+1;
    f[now][0]=fa;
    for(int i=1;i<=lg[d[now]];++i)
        f[now][i]=f[f[now][i-1]][i-1];
    for(auto i:e[now])dfs(i,now);
}
void dfs_ans(int now){
    if(vis[now])return;
    vis[now]=true;
    for(auto i:e[now]){
        if(!vis[i]){//一定要加这一句,不然下面p[now]会累计父节点的值
            dfs_ans(i);
            p[now]+=p[i];
        }
    }
    ans=max(ans,p[now]);
}
int main(){
    n=read(),k=read();
    for(int i=1,x,y;i<=n-1;++i){
        x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }

    for(int i=1;i<=n;++i){
        lg[i]=log(i)/log(2)+1;
    }
    dfs(1,1);
    for(int i=1,s,t;i<=k;++i){
        s=read(),t=read();
        int fa=lca(s,t);
        p[s]++,p[t]++,p[fa]--,p[f[fa][0]]--;
    }

    vis.reset();
    dfs_ans(1);
    cout<<ans<<endl;
    return 0;
}

这里面有个坑，用子节点往父节点传递信息的时候，如果是STL开的邻接表一定一定要记得在循环里面加一下父节点的判断，不然debug找两年   ：(

包括传递子节点数量这种树上dp也一样。