头像

神秘刀光男




离线:1天前


最近来访(169)
用户头像
ligg
用户头像
霊梦
用户头像
DreamDimo
用户头像
西山红叶生
用户头像
incra
用户头像
Dist
用户头像
我是菜狗啊啊啊啊啊
用户头像
Mhcc
用户头像
yxc_助手1387号
用户头像
我是小学生奖牌发给我
用户头像
夜雨听笛
用户头像
小小_88
用户头像
gsea37
用户头像
waydedie
用户头像
abincaps
用户头像
不落虚.
用户头像
xiaoxiaosky
用户头像
山猪
用户头像
Ncik
用户头像
Daisy_西西

活动打卡代码 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;
}


活动打卡代码 AcWing 402. 杀人游戏

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=6e5+10;
int n,m,idx,ts,scc_cnt,flag;
int e[M],ne[M],h[N],hs[N],d[N],st[N];
int dfn[N],low[N],siz[N],id[N];
int stk[N],in_stk[N],top;
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++ts;
    stk[++top]=u;
    in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]){
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        int t;
        scc_cnt++;
        do{
            t=stk[top--];
            in_stk[t]=0;
            siz[scc_cnt]++;
            id[t]=scc_cnt;
        }while(t!=u);
    }
}
bool check(int scc){
    if(flag)return false;
    for(int i=hs[scc];~i;i=ne[i]){
        int j=e[i];
        if(d[j]<2)return false;
    }
    return true;
}
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);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    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||st[b])continue;
            add(hs,a,b);
            d[b]++;
            st[b]=1;
        }
        for(int j=h[i];~j;j=ne[j])st[id[e[j]]]=0;
    }
    int res=0;
    for(int i=1;i<=scc_cnt;i++){
        if(d[i])continue;
        res++;
        if(siz[i]>1)continue;
        if(check(i))flag=1;
    }
    if(flag)res--;
    printf("%.6lf",1.0*(n-res)/n);
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



算法1

(线段树) $O(nlogn)$

从后往前用线段树维护最大的下标

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Tree{
    int l,r,mx;
}tr[N*4];
int a[N],n,res[N];
vector<int>num;
void pushup(int u){
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void build(int u,int l,int r){
    tr[u]={l,r,0};
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int x,int c){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].mx=max(tr[u].mx,c);
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid)modify(u<<1,x,c);
    else modify(u<<1|1,x,c);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].mx;
    int res=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)res=max(res,query(u<<1,l,r));
    if(r>mid)res=max(res,query(u<<1|1,l,r));
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],num.emplace_back(a[i]);
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(num.begin(),num.end(),a[i])-num.begin()+1;//离散化一下
    build(1,1,num.size());
    for(int i=n;i;i--){
        modify(1,a[i],i);
        int t=query(1,1,a[i]-1);
        if(!t)res[i]=-1;
        else res[i]=t-i-1;
    } 
    for(int i=1;i<=n;i++)cout<<res[i]<<" ";
    return 0;
} 



活动打卡代码 AcWing 404. 婚礼

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=2*N;
int n,m,idx,ts,scc_cnt;
int e[M],ne[M],h[N],op[N];
int dfn[N],low[N],id[N];
int stk[N],in_stk[N],top;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++ts;
    stk[++top]=u,in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]){
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        scc_cnt++; 
        int t;
        do{
            t=stk[top--];
            in_stk[t]=0;
            id[t]=scc_cnt;
        }while(u!=t);
    }
}
bool check(){
    for(int i=0;i<n;i++){
        if(id[i]==id[i+n])return true;
    }
    return false;
}
int main(){
    while(scanf("%d%d",&n,&m),n||m){
        for(int i=0;i<n;i++)op[i]=i+n,op[i+n]=i;
        scc_cnt=idx=ts=0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        int a,b;
        char c,d;
        add(0,n);
        while(m--){
            scanf("%d%c %d%c",&a,&c,&b,&d);
            if(c=='h')a+=n;
            if(d=='h')b+=n;
            add(a,op[b]),add(b,op[a]);
        }
        for(int i=0;i<2*n;i++){
            if(!dfn[i])tarjan(i);
        }
        if(check())puts("bad luck");
        else{
            for(int i=1;i<n;i++){
                printf("%d",i);
                if(id[i]>id[i+n])printf("w ");
                else printf("h ");
            }
            puts("");
        }
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 353. 雨天的尾巴

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using PII=pair<int,int>;
const int N=1e5+10,M=2*N;
int n,m,idx,cnt;
int e[M],ne[M],h[N],u[N],v[N],c[N];
int fa[N],son[N],dep[N],siz[N];
int top[N],id[N],mp[N],res[N];
struct Tree{
    int l,r,k;
    LL cnt;
}tr[N*4];
vector<int>num; 
vector<int>reg[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==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    if(tr[u<<1].cnt>=tr[u<<1|1].cnt){
        tr[u].k=tr[u<<1].k;
        tr[u].cnt=tr[u<<1].cnt;
    }
    else{
        tr[u].k=tr[u<<1|1].k;
        tr[u].cnt=tr[u<<1|1].cnt;
    }
}
void build(int u,int l,int r){
    tr[u]={l,r,l,0};
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int x,int k){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].cnt+=k;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid)modify(u<<1,x,k);
    else modify(u<<1|1,x,k);
    pushup(u);
}
void update_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        reg[id[top[u]]].push_back(k),reg[id[u]+1].push_back(-k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    reg[id[v]].push_back(k),reg[id[u]+1].push_back(-k);
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs1(1,-1,1),dfs2(1,1),build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",u+i,v+i,c+i);
        num.emplace_back(c[i]); 
    }
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    for(int i=1;i<=m;i++){
        update_path(u[i],v[i],lower_bound(num.begin(),num.end(),c[i])-num.begin()+1);
    }
    for(int i=1;i<=n;i++){
        for(auto t:reg[i]){
            if(t>0)modify(1,t,1);
            else modify(1,-t,-1);
        }
        res[mp[i]]=tr[1].cnt?num[tr[1].k-1]:0;
    }
    for(int i=1;i<=n;i++)printf("%d\n",res[i]);
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~