洛谷 P3128 [USACO15DEC] Max Flow P

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

---

前置知识，LCA模板

洛谷 P3379 【模板】最近公共祖先（LCA）-CSDN博客

读题注意

从隔间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 
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];
bitsetvis;
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]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<
    return 0;
}

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

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

既然倍增LCA能过，那么不得不试一下用线段树维护欧拉序求LCA了

查询都是log级别，只是线段树的常数会大一点，代码会多一点。

AC代码（线段树维护欧拉序+树上差分）

#include 
using namespace std;
const int N=5e4+5;
 
int n,k,p[N],res,f[N],idx[N<<1],st[N<<3],oula[N<<1],oulan,d[N];
vector<int>e[N];
bitsetvis;
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;
}
void dfs(int x){
    if(vis[x])return;
    vis[x]=true;
    oula[++oulan]=x;
    if(!idx[x])idx[x]=oulan;
    for(auto i:e[x]){
        if(!vis[i]){//用STL写的千万别忘了加这个，不然无向图会累计父节点
            f[i]=x;//最好所有dfs都加这个判断。
            d[i]=d[x]+1;
            dfs(i);
            oula[++oulan]=x;
            if(!idx[x])idx[x]=oulan;
        }
    }
}
void build(int l,int r,int i){
    if(l==r){
        st[i]=oula[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    st[i]=d[st[i<<1]]1|1]]?st[i<<1]:st[i<<1|1];
}
int lca(int l,int r,int i,int x,int y){
    int ans=0;
    if(l>=x and r<=y)return st[i];
    int mid=(l+r)>>1;
    if(x<=mid){
        int t=lca(l,mid,i<<1,x,y);
        if(d[t]
    }
    if(y>mid){
        int t=lca(mid+1,r,i<<1|1,x,y);
        if(d[t]
    }
    return ans;
}
void dfs_res(int x){
    if(vis[x])return;
    vis[x]=true;
    for(auto i:e[x]){
        if(!vis[i]){
            dfs_res(i);
            p[x]+=p[i];
        }
    }
    res=max(p[x],res);
}
 
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);
    }
 
    dfs(1);
    build(1,oulan,1);
    d[0]=INT_MAX;
 
    for(int i=1,s,t;i<=k;++i){
        s=read(),t=read();
        int l=idx[s],r=idx[t],LCA;
        if(l>r)swap(l,r);
        LCA=lca(1,oulan,1,l,r);
        p[s]++,p[t]++,p[LCA]--,p[f[LCA]]--;
    }
 
    vis.reset();
    dfs_res(1);
    cout<
    return 0;
}