Luogu P3128 [USACO15DEC]最大流Max Flow

March 9, 2019

1188 views

795 words

[题目链接](https://www.luogu.org/problemnew/show/P3128) 

这几天在学LCA，这道题使用了LCA+树上差分的思路。 题目描述，每经过一次的点就会加1，换言之，就是统计每一个节点经过了多少次，所以可以使用树上差分快速得到每个点经过的次数。 我们可以这样统计：如果x和y之间有一条路径，那么可以看做x->lca(x,y),lca(x,y)->y；两条路径各自分别加1，但是这样lca（x，y）会被加两遍，所以cnt\[x\]++,cnt\[y\]++,cnt\[lca(x,y)\]-=2。 但是这样一来，lca(u,v)上+2又-2等于0，也就是u--->v整条路经上除了lca(u,v)都加了1，为了排除这个干扰，我们把cnt\[lca(u,v)\]-=2改成- -cnt\[lca(u,v)\],- -cnt\[lca(u,v)的父亲\]
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    int tot,head[50009],n,m,s,d[50009],f[50009][20],t,lg[50009],cnt[50009];
    struct Edge{
        int to,next;
    }e[100009];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    void dfs(int y,int x){
        d[y]=d[x]+1;
        f[y][0]=x;
        for(int i=1;(1<<i)<=d[y];i++) f[y][i]=f[f[y][i-1]][i-1];
        for(int i=head[y];i;i=e[i].next) if(e[i].to!=x) dfs(e[i].to,y);
    }
    
    void dfs_sum(int u,int fa){
        for(int i=head[u];i;i=e[i].next){
            int y=e[i].to;
            if(y==fa) continue;
            dfs_sum(y,u);
            cnt[u]+=cnt[y];
        }
    }
    
    int lca(int x,int y){
        if(d[x]>d[y]) swap(x,y);
        while(d[x]<d[y]) y=f[y][lg[d[y]-d[x]]-1];
        if(x==y) return x;
        for(int i=lg[d[x]]-1;i>=0;i--) if(f[x][i]!=f[y][i]) y=f[y][i],x=f[x][i];
        return f[x][0];
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        dfs(1,0);
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            int lcas=lca(x,y);
            cnt[x]++,cnt[y]++,cnt[lcas]--,cnt[f[lcas][0]]--;
        }
        dfs_sum(1,0);
        int maxn=0;
        for(int i=1;i<=n;i++) maxn=max(maxn,cnt[i]);
        cout<<maxn;
        return 0;
    }
```

Last modification：March 14, 2020