求调

已经被这道题卡了四天了。。。

在 codeforces 交wa 第7个点

#include<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define push_back emplace_back
#define int long long
constexpr int N=2e5+5,M=2e5+5;

int n,m,x,y,z;
int fat[N],fa[N],f[N][22],dep[N],mx[N][22],lg[N];
int fa_len[N],sfa[N],zx[N];
int ans[N],tot,cnt;
bitset<N> mark;

struct edge {
    int x,y,z,id;
} a[N],b[N],c[N],ya[N];

bool _cmp1(edge a,edge b) {
    return a.z <b.z;
}

int getfa(int x) {
    return x==fat[x]?x:fat[x]=getfa(fat[x]);
}
void mix(int x,int y) {
    fat[x]=y;
}

vector<int>now_g[M];
vector<int>g[M];
vector<int>_long[M];

void build(int x) {
    mark[x]=true;
    mx[x][0]=lg[fa_len[x]];
    f[x][0]=sfa[x];
    for(int i=1; i<=21; i++)f[x][i]=f[f[x][i-1]][i-1],mx[x][i]=max(mx[f[x][i-1]][i-1],mx[x][i-1]);
    for(int i=0; i<now_g[x].size(); i++) {
        if(mark[now_g[x][i]])continue;
        //  cout<<ya[_long[x][i]].x <<" "<<ya[_long[x][i]].y <<" "<<ya[_long[x][i]].z<<endl;
        g[x].push_back(now_g[x][i]);
        sfa[now_g[x][i]]=x;
        dep[now_g[x][i]]=dep[x]+1;
        fa_len[now_g[x][i]]=_long[x][i];
        build(now_g[x][i]);
    }
}

int LCA_or_ST(int x,int y,bool wa) {
    int ans=0;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=21; i>=0; i--)
        if(dep[f[x][i]]>=dep[y])ans=max(ans,mx[x][i]),x=f[x][i];
    if(x==y)return wa?ans:x;
    for(int i=21; i>=0; i--)
        if(f[x][i]!=f[y][i]) {
            ans=max(ans,max(mx[x][i],mx[y][i]));
            x=f[x][i];
            y=f[y][i];
        }
    return wa?max(ans,max(mx[x][0],mx[y][0])):f[x][0];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//freopen("IN.in","r",stdin);
    memset(ans,0x3f,sizeof(ans));
    dep[1]=1;
    cin>>n>>m;
    for(int i=1; i<=n; i++)fat[i]=sfa[i]=i;
    for(int i=1; i<=m; i++) {
        cin>>x>>y>>z;
        ya[i]=a[i]=(edge) {
            x,y,z,i
        };
    }
    sort(a+1,a+m+1,_cmp1);
    for(int i=1; i<=m; i++) {
        lg[a[i].id]=a[i].z;
        x=getfa(a[i].x),y=getfa(a[i].y);
        if(x!=y) {
            c[++tot]=a[i];
            mix(x,y);
            now_g[a[i].x].push_back(a[i].y);
            now_g[a[i].y].push_back(a[i].x);
            _long[a[i].x].push_back(a[i].id);
            _long[a[i].y].push_back(a[i].id);
        } else b[++cnt]=a[i];
    }
    build(1);
    sort(b+1,b+cnt+1,_cmp1);
    for(int i=1; i<=cnt; i++) {
        x=b[i].x ,y=b[i].y ,z=b[i].z ;
        int s=LCA_or_ST(x,y,0);
        while(dep[x]>dep[s]) {
            ans[fa_len[x]]=min(ans[fa_len[x]],z-1);
            int yy=x;
            x=sfa[x];
            sfa[yy]=s;
        }
        sfa[b[i].x ]=s;
        while(dep[y]>dep[s]) {
            ans[fa_len[y]]=min(ans[fa_len[y]],z-1);
            int yy=y;
            y=sfa[y];
            sfa[yy]=s;
        }
        sfa[b[i].y ]=s;
        ans[b[i].id ]=LCA_or_ST(b[i].x ,b[i].y ,1)-1;
    }
    int qe=m;
    //io.read(qe);
    for(int i=1; i<=qe; i++) {
        //  io.read(x);
        x=i;
        if(ans[x]>=0x3f3f3f3f)ans[x]=-1;
        cout<<ans[x]<<endl;
    }
    return 0;
}
*/