头像

神秘刀光男




离线:23分钟前


最近来访(173)
用户头像
呐呐呐呐
用户头像
霊梦
用户头像
ACdefly
用户头像
ligg
用户头像
DreamDimo
用户头像
西山红叶生
用户头像
incra
用户头像
Dist
用户头像
我是菜狗啊啊啊啊啊
用户头像
Mhcc
用户头像
yxc_助手1387号
用户头像
清风飘扬
用户头像
夜雨听笛
用户头像
小小_88
用户头像
gsea37
用户头像
waydedie
用户头像
abincaps
用户头像
不落虚.
用户头像
xiaoxiaosky
用户头像
山猪


#include<bits/stdc++.h>
using namespace std;
const int N=550,M=1e4+10,INF=0x3f3f3f3f;
int n,m,S,T,idx,res;
int e[M],ne[M],h[N],f[M];
int st_s[N],st_t[N],d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
}
bool bfs(){
    memset(d,-1,sizeof d);
    d[S]=1,cur[S]=h[S];
    queue<int>q;
    q.push(S);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]==-1&&f[i]){
                d[j]=d[t]+1;
                cur[j]=h[j];
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int j=e[i];
        cur[u]=i;
        if(d[j]==d[u]+1&&f[i]){
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int res=0,flow;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
void dfs(int u,int st[],int t){
    st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(f[i^t]&&!st[j]){
            dfs(j,st,t);
        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0,T=n-1;
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,0);
    }
    dinic();
    dfs(S,st_s,0);
    dfs(T,st_t,1);
    for(int i=0;i<2*m;i+=2){
        if(!f[i]&&st_s[e[i^1]]&&st_t[e[i]])res++;
    }
    printf("%d",res);
    return 0;
} 
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



没人写树剖解法补一下

算法1

(Tarjan+树链剖分) $O(N+M+qlogn)$

tarjan缩点后变成一棵树,令桥的边权为1,建树的时候把边权转化为点权,即深点权对应着边权。

每次询问原图两个点之间增加一条边转化为向树中的两个新点(双连通分量)加一条边,向树中加边后意味着树中两个点间路径的桥都无了,对应着区间桥的数量变成0,之后再区间查询桥的数量就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
const int N=2e5+10,M=1e6;
int n,m,idx,q,x,dcc_cnt,ts,cnt;
int e[M],ne[M],h[N],hs[N],w[N];
int dfn[N],low[N];
int stk[N],tp;
int did[N],id[N],mp[N];
int fa[N],son[N];
int dep[N],top[N],siz[N];
vector<PII>edg;
struct Tree{
    int l,r,sum,lazy;//sum求路径上桥的数量,lazy区间改懒标记
}tr[N*4];
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++ts;
    stk[++tp]=u;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
        }
        else if(i!=(from^1))low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u]){
        int t;
        dcc_cnt++;
        do{
            t=stk[tp--];
            did[t]=dcc_cnt;
        }while(u!=t);
    }
}
void dfs1(int u,int father,int depth){
    siz[u]=1,fa[u]=father,dep[u]=depth;
    for(int i=hs[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u,depth+1);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j])son[u]=j;//找重儿子
    }
}
void dfs2(int u,int t){
    id[u]=++cnt,top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=hs[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(~root.lazy){
        left.lazy=right.lazy=root.lazy;
        left.sum=right.sum=root.lazy;
        root.lazy=-1;
    }
}
void build(int u,int l,int r){
    tr[u]={l,r,w[l],-1};//加一条边会让路径上的桥数量变为0,对应区间修改成0,懒标记初始成-1
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int k){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum=k;
        tr[u].lazy=k;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)update(u<<1,l,r,k);
    if(r>mid)update(u<<1|1,l,r,k);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    pushdown(u);
    int res=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)res+=query(u<<1,l,r);
    if(r>mid)res+=query(u<<1|1,l,r);
    return res;
}
void update_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update(1,id[v]+1,id[u],k);//注意最浅的点不能算,因为他的点权对应着他和父亲节点之间的边权
}
int main(){
    while(scanf("%d%d",&n,&m),n||m){
        memset(h,-1,sizeof h);
        memset(hs,-1,sizeof hs);
        memset(dfn,0,sizeof dfn);
        memset(son,0,sizeof son);
        idx=ts=dcc_cnt=cnt=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            add(h,a,b),add(h,b,a);
        }
        tarjan(1,-1);
        for(int i=1;i<=n;i++){
            for(int j=h[i];~j;j=ne[j]){
                int k=e[j];
                int a=did[i],b=did[k];
                if(a==b)continue;
                w[a]=w[b]=0;
                add(hs,a,b);
                //add(hs,b,a),千万别加,这样会建重边(两条重复的无向边),dfs2时会把点编号标乱掉
                edg.emplace_back(a,b);
            }
        }
        dfs1(1,-1,1),dfs2(1,-1);
        for(auto [u,v]:edg){
            if(dep[u]<dep[v])swap(u,v);
            w[u]=1;//深点对应的边一定是唯一的,树边全是桥,把边权转化成点权
        }
        build(1,1,dcc_cnt);
        printf("Case %d:\n",++x);
        scanf("%d",&q);
        while(q--){
            int a,b;
            scanf("%d%d",&a,&b);
            a=did[a],b=did[b];
            if(a!=b)update_path(a,b,0);
            printf("%d\n",query(1,1,dcc_cnt));
        }
        puts("");
    }
    return 0;
}

算法2

(Tarjan+倍增LCA+(并查集))


活动打卡代码 AcWing 364. 网络

#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
const int N=2e5+10,M=1e6;
int n,m,idx,q,x,dcc_cnt,ts,cnt;
int e[M],ne[M],h[N],hs[N],w[N];
int dfn[N],low[N];
int stk[N],tp;
int did[N],id[N],mp[N];
int fa[N],son[N];
int dep[N],top[N],siz[N];
vector<PII>edg;
struct Tree{
    int l,r,sum,lazy;
}tr[N*4];
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++ts;
    stk[++tp]=u;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
        }
        else if(i!=(from^1))low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u]){
        int t;
        dcc_cnt++;
        do{
            t=stk[tp--];
            did[t]=dcc_cnt;
        }while(u!=t);
    }
}
void dfs1(int u,int father,int depth){
    siz[u]=1,fa[u]=father,dep[u]=depth;
    for(int i=hs[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u,depth+1);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j])son[u]=j;
    }
}
void dfs2(int u,int t){
    id[u]=++cnt,top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=hs[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(~root.lazy){
        left.lazy=right.lazy=root.lazy;
        left.sum=right.sum=root.lazy;
        root.lazy=-1;
    }
}
void build(int u,int l,int r){
    tr[u]={l,r,w[l],-1};
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int k){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum=k;
        tr[u].lazy=k;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)update(u<<1,l,r,k);
    if(r>mid)update(u<<1|1,l,r,k);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    pushdown(u);
    int res=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)res+=query(u<<1,l,r);
    if(r>mid)res+=query(u<<1|1,l,r);
    return res;
}
void update_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update(1,id[v]+1,id[u],k);
}
int main(){
    while(scanf("%d%d",&n,&m),n||m){
        memset(h,-1,sizeof h);
        memset(hs,-1,sizeof hs);
        memset(dfn,0,sizeof dfn);
        memset(son,0,sizeof son);
        idx=ts=dcc_cnt=cnt=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            add(h,a,b),add(h,b,a);
        }
        tarjan(1,-1);
        for(int i=1;i<=n;i++){
            for(int j=h[i];~j;j=ne[j]){
                int k=e[j];
                int a=did[i],b=did[k];
                if(a==b)continue;
                w[a]=w[b]=0;
                add(hs,a,b);
                edg.emplace_back(a,b);
            }
        }
        dfs1(1,-1,1),dfs2(1,-1);
        for(auto [u,v]:edg){
            if(dep[u]<dep[v])swap(u,v);
            w[u]=1;
        }
        build(1,1,dcc_cnt);
        printf("Case %d:\n",++x);
        scanf("%d",&q);
        while(q--){
            int a,b;
            scanf("%d%d",&a,&b);
            a=did[a],b=did[b];
            if(a!=b)update_path(a,b,0);
            printf("%d\n",query(1,1,dcc_cnt));
        }
        puts("");
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4539. 食物

#include<bits/stdc++.h>
using namespace std;
const int N=1e3,M=2e5,INF=0x3f3f3f3f;
int n,m,k,S,T,idx;
int e[M],ne[M],h[N],f[M];
int cur[N],d[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
}
bool bfs(){
    memset(d,-1,sizeof d);
    d[S]=1,cur[S]=h[S];
    queue<int>q;
    q.push(S);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]==-1&&f[i]){
                d[j]=d[t]+1;
                cur[j]=h[j];
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int j=e[i];
        cur[u]=i;
        if(d[j]==d[u]+1&&f[i]){
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int res=0,flow;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        S=0,T=2*n+m+k+1;
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=1;i<=m;i++){
            int x;
            scanf("%d",&x);
            add(S,i,x),add(i,S,0);
        }
        for(int i=1;i<=k;i++){
            int x;
            scanf("%d",&x);
            add(m+2*n+i,T,x),add(T,m+2*n+i,0);
        }
        for(int i=1;i<=n;i++)add(m+i,m+n+i,1),add(m+n+i,m+i,0);
        char op[220];
        for(int i=1;i<=n;i++){
            scanf("%s",op+1);
            for(int j=1;j<=m;j++){
                if(op[j]=='Y')add(j,m+i,1),add(m+i,j,0);
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%s",op+1);
            for(int j=1;j<=k;j++){
                if(op[j]=='Y')add(m+n+i,m+2*n+j,1),add(m+2*n+j,m+n+i,0);
            }
        }
        printf("%d\n",dinic());
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4538. 岛屿交通

#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;
int n,m,S,T,idx,t;
int e[M],ne[M],h[N],f[M];
int cur[N],d[N],pos[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
}
bool bfs(){
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    queue<int>q;
    q.push(S);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]==-1&&f[i]){
                d[j]=d[t]+1;
                cur[j]=h[j];
                if(j==T)return true;
                q.push(j);
            }
        } 
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int j=e[i];
        cur[u]=i;
        if(d[j]==d[u]+1&&f[i]){
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int flow,res=0;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
int main(){
    scanf("%d",&t);
    while(t--){
        idx=0;
        memset(h,-1,sizeof h);
        scanf("%d%d",&n,&m);
        int mx=-INF,mn=INF;
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            pos[i]=a;
            if(mx<a){
                mx=a,T=i;
            }
            if(mn>a){
                mn=a,S=i;
            }
        }
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c),add(b,a,c);
        }
        printf("%d\n",dinic());
    }
    return 0;
} 
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


分享 小笔记

https://www.luogu.com.cn/problem/P8025

一道卡倍增不卡树剖的题,让我深刻理解了倍增常数较大,以及树剖优越性。

倍增T了一个点

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,k,idx;
int e[M],ne[M],h[N],res[N];
int depth[N],fa[N][20];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){
    memset(depth,0x3f,sizeof depth);
    depth[1]=1,depth[0]=0;
    queue<int>q;
    q.push(1);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=19;k++){
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    } 
}
int lca(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    for(int k=19;k>=0;k--){
        if(depth[fa[a][k]]>=depth[b]){
            a=fa[a][k];
        }
    }
    if(a==b)return a;
    for(int k=19;k>=0;k--){
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    bfs();
    for(int i=0;i<k;i++){
        int d,t;
        scanf("%d%d",&d,&t);
        int anc=lca(m,d);
        int dis=depth[m]+depth[d]-2*depth[anc];
        if(dis<=t)m=d;
        else{
            int dist=depth[m]-depth[anc];
            if(t<=dist)
            for(int k=19;k>=0;k--){
                if(t>>k&1)m=fa[m][k];
            }
            else{
                m=d,dist=dis-t;
                for(int k=19;k>=0;k--){
                    if(dist>>k&1)m=fa[m][k];
                }
            }
        }
        printf("%d ",m);
    }
    return 0;
}

树剖AC

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,k,idx,cnt;
int e[M],ne[M],h[N];
int siz[N],son[N],fa[N];
int dep[N],top[N],mp[N],id[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father,int depth){
    siz[u]=1,fa[u]=father,dep[u]=depth;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u,depth+1);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j])son[u]=j;
    }
}
void dfs2(int u,int t){
    id[u]=++cnt,mp[cnt]=u,top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==son[u]||j==fa[u])continue;
        dfs2(j,j);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    return v;
}
int move(int u,int depth){
    depth=dep[u]-depth;
    while(dep[top[u]]>depth){
        u=fa[top[u]];
    }
    return mp[id[u]-(dep[u]-depth)];
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs1(1,-1,1),dfs2(1,1);
    while(k--){
        int d,t;
        scanf("%d%d",&d,&t);
        int anc=lca(m,d);
        int dis=dep[m]+dep[d]-2*dep[anc];
        if(dis<=t)m=d;//m能到d
        else{
            if(dep[m]-dep[anc]>=t)m=move(m,t);//在m到LCA上
            else m=move(d,dis-t);//在d到LCA上
        }
        printf("%d ",m);
    }
    return 0;
}


活动打卡代码 AcWing 397. 逃不掉的路

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=8e5+10;
int n,m,q,idx,ts,dcc_cnt;
int e[M],ne[M],h[N],hs[N],w[M];
int dfn[N],low[N],id[N];
int stk[N],top;
int fa[N][17],depth[N];
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++ts;
    stk[++top]=u;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
        }
        else if(i!=(from^1)){
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        dcc_cnt++;
        int t;
        do{
            t=stk[top--];
            id[t]=dcc_cnt;
        }while(t!=u);
    }
}
void bfs(){
    memset(depth,-1,sizeof depth);
    depth[0]=0,depth[1]=1;
    queue<int>q;
    q.push(1);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=hs[t];~i;i=ne[i]){
            int j=e[i];
            if(depth[j]==-1){
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=16;k++){
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    for(int k=16;k>=0;k--){
        if(depth[fa[a][k]]>=depth[b]){
            a=fa[a][k];
        }
    }
    if(a==b)return a;
    for(int k=16;k>=0;k--){
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}
int main(){
    memset(hs,-1,sizeof hs);
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b),add(h,b,a);
    }
    tarjan(1,-1);
    for(int i=1;i<=n;i++){
        for(int j=h[i];~j;j=ne[j]){
            int k=e[j];
            int a=id[i],b=id[k];
            if(a==b)continue;
            add(hs,a,b),add(hs,b,a);
        }
    } 
    bfs();
    scanf("%d",&q);
    while(q--){
        int a,b;
        scanf("%d%d",&a,&b);
        int anc=lca(id[a],id[b]);
        printf("%d\n",depth[id[a]]+depth[id[b]]-2*depth[anc]);
    }
    return 0;
} 
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2234. 多源汇最大流

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2e5+4*N,INF=0x3f3f3f3f;
int n,m,sc,tc,S,T,idx;
int e[M],ne[M],h[N],f[M];
int cur[N],d[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
}
bool bfs(){
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    queue<int>q;
    q.push(S);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]==-1&&f[i]){
                d[j]=d[t]+1;
                cur[j]=h[j];
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i]){
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int res=0,flow;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&sc,&tc);
    S=0,T=n+1;
    while(sc--){
        int x;
        scanf("%d",&x);
        add(S,x,INF),add(x,S,0);
    }
    while(tc--){
        int x;
        scanf("%d",&x);
        add(x,T,INF),add(T,x,0);
    }
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,0);
    }
    printf("%d",dinic());
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 412. 排水沟

#include<bits/stdc++.h>
using namespace std;
const int N=220,M=2*N,INF=0x3f3f3f3f;
int n,m,S,T,idx;
int e[M],ne[M],h[N],f[M];
int cur[N],d[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
}
bool bfs(){
    memset(d,-1,sizeof d);
    d[S]=1,cur[S]=h[S];
    queue<int>q;
    q.push(S);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]==-1&&f[i]){
                cur[j]=h[j];
                d[j]=d[t]+1;
                if(j==T)return true;
                q.push(j);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int j=e[i];
        cur[u]=i;
        if(d[j]==d[u]+1&&f[i]){
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    } 
    return flow; 
}
int dinic(){
    int res=0,flow;
    while(bfs())while(flow=find(S,INF))res+=flow;
    return res;
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);    
    S=1,T=n;
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,0);
    }
    printf("%d",dinic());
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



https://www.luogu.com.cn/problem/P4315

调了一下午 人裂开了

#include<bits/stdc++.h>
using namespace std;
using PII=pair<int,int>;
const int N=1e5+10,M=2*N;
int n,idx,cnt;
int e[M],ne[M],h[N],w[M],a[N],nw[N];
int fa[N],son[N],siz[N];
int dep[N],top[N],id[N];
vector<PII>p;
struct Tree{
    int l,r,mx,add,c;
}tr[N*4];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs1(int u,int father,int depth){
    siz[u]=1,fa[u]=father,dep[u]=depth;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        a[j]=w[i];
        //w[j]=w[i];把边权给点要新开个数组,这样明显是错的,没看出来,调了一下午...
        dfs1(j,u,depth+1);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j])son[u]=j;
    }
}
void dfs2(int u,int t){
    id[u]=++cnt,nw[cnt]=a[u],top[u]=t;
    //nw[cnt]=w[u];
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void pushdown(int u){
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(~root.c){
        left.c=right.c=root.c;
        left.add=right.add=0;//全部修改成一个数一定记得把"增加"懒标记清空
        left.mx=right.mx=root.c;
        root.c=-1;
    }   
    if(root.add){
        left.add+=root.add;
        right.add+=root.add;
        left.mx+=root.add;
        right.mx+=root.add;
        root.add=0;
    }
}
void build(int u,int l,int r){
    tr[u]={l,r,nw[l],0,-1};
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void update1(int u,int l,int r,int v){//区间改
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].mx=v;
        tr[u].c=v;
        tr[u].add=0;//注意清空"增加"懒标记
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)update1(u<<1,l,r,v);
    if(r>mid)update1(u<<1|1,l,r,v);
    pushup(u);
}
void update2(int u,int l,int r,int v){//区间加
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].add+=v;
        tr[u].mx+=v;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)update2(u<<1,l,r,v);
    if(r>mid)update2(u<<1|1,l,r,v);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].mx;
    pushdown(u);
    int mx=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)mx=max(mx,query(u<<1,l,r));
    if(r>mid)mx=max(mx,query(u<<1|1,l,r));
    return mx; 
}
void update_path1(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update1(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update1(1,id[v]+1,id[u],k);//树枝的边权是深层的点权,高点的编号注意加1,下面同理
}
void update_path2(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update2(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update2(1,id[v]+1,id[u],k);
}
int query_path(int u,int v){
    int res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=max(res,query(1,id[top[u]],id[u]));
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    res=max(res,query(1,id[v]+1,id[u]));
    return res;
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
        p.emplace_back(a,b);
    }
    dfs1(1,-1,1),dfs2(1,1),build(1,1,n);
    char op[10];
    int u,v,x;
    while(scanf("%s",op),*op!='S'){
        scanf("%d",&u);
        if(op[1]=='o'){
            scanf("%d%d",&v,&x);
            update_path1(u,v,x);
        }
        else if(op[1]=='d'){
            scanf("%d%d",&v,&x);
            update_path2(u,v,x);
        }
        else if(op[1]=='h'){
            scanf("%d",&x);
            int a=p[u-1].first,b=p[u-1].second;
            if(dep[a]<dep[b])swap(a,b);//树枝的边权是深层的点权
            update1(1,id[a],id[a],x);
        }
        else{
            scanf("%d",&v);
            printf("%d\n",query_path(u,v));
        }
    } 
    return 0;
}