AC了#1，剩下全WA，悬关求调

QCurium @ 2023-09-02 10:32:30

#include<bits/stdc++.h>
#define int long long
#define base 200807
#define mod 212370440130137903
using namespace std;
const int N=1e5+5;
int n,tot=0,cnt=0;
int head[N],dep[N],siz[N],fa[N],w[N],dfn[N],son[N],top[N],ba[N];
struct edge{
    int to,next,z,ii;
}e[N*2];
struct node{
    int l,r;
    int sum,mx;
}a[N*4];
///////////////////////////////////////
void ade(int u,int v,int w,int sa){
    e[tot]=(edge){v,head[u],w,sa};
    head[u]=tot++;
    e[tot]=(edge){u,head[v],w,sa};
    head[v]=tot++;
    return ;
}
void dfs1(int nw,int f){
    fa[nw]=f;
    dep[nw]=dep[f]+1;
    siz[nw]=1;
    int asd=-1;
    for(int i=head[nw];~i;i=e[i].next){
        int er=e[i].to;
        if(er==f)
            continue;
        dfs1(er,nw);
        siz[nw]+=siz[er];
        if(siz[er]>asd){
            asd=siz[er];
            son[nw]=er;
        }
    }
    return ;
}
void dfs2(int nw,int t){
    dfn[nw]=++cnt;
    top[nw]=t;
    if(!son[nw])
        return ;
    dfs2(son[nw],t); 
    for(int i=head[nw];~i;i=e[i].next){
        int er=e[i].to;
        if(er==son[nw]){
            w[dfn[er]]=e[i].z;
            ba[e[i].ii]=dfn[er];
            continue;
        }
        if(er==fa[nw])
            continue;
        dfs2(er,er);
        w[dfn[er]]=e[i].z;
        ba[e[i].ii]=dfn[er];
    }
    return ;
}
///////////////////////////////////////
void push_up(int aa){
    a[aa].mx=max(a[aa*2].mx,a[aa*2+1].mx);
    return ;
}
void build(int aa,int l,int r){
    a[aa].l=l;
    a[aa].r=r;
    if(l==r){
        a[aa].sum=w[l];
        a[aa].mx=a[aa].sum;
        return ;
    }
    int mid=(l+r)>>1;
    build(aa*2,l,mid);
    build(aa*2+1,mid+1,r);
    push_up(aa);
    return ;
}
void modify(int aa,int lr,int z){
    if(a[aa].l==a[aa].r&&a[aa].l==lr){
        a[aa].sum=z;
        a[aa].mx=z;
        return ;
    }
    int mid=(a[aa].l+a[aa].r)>>1;
    if(lr<=mid)
        modify(aa*2,lr,z);
    else
        modify(aa*2+1,lr,z);
    push_up(aa);
    return ;
}
int query(int aa,int l,int r){
    if(a[aa].l>=l&&a[aa].r<=r)
        return a[aa].mx;
    int ans=-2147483647,mid=(a[aa].l+a[aa].r)>>1;
    if(l<=mid)
        ans=max(ans,query(aa*2,l,r));
    if(r>mid)
        ans=max(ans,query(aa*2+1,l,r));
    return ans;
}
///////////////////////////////////////
int qchain(int x,int y){
    int ans=-2147483647;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans=max(ans,query(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(top[x]>top[y])
        swap(x,y);
    ans=max(ans,query(1,dfn[x]+1,dfn[y]));
    return ans;
}
///////////////////////////////////////
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,h;
        cin>>u>>v>>h;
        ade(u,v,h,i);
    }
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
//  for(int i=1;i<=n;i++)
//      cout<<ba[i]<<'\n';
    while(1){
        string asd;
        int aa,bb;
        cin>>asd;
        if(asd[0]=='D')
            break;
        if(asd[0]=='C'){
            cin>>aa>>bb;
            modify(1,ba[aa],bb);
        }
        else{
            cin>>aa>>bb;
            if(aa>bb)
                swap(dfn[aa],dfn[bb]);
            if(aa==bb)
                cout<<0<<" asd"<<'\n';
            else
                cout<<qchain(aa,bb)<<'\n';
        }
    }
    return 0;
}

by Y2y7m @ 2023-09-02 10:52:18

@quchenming

if(aa>bb)
                swap(dfn[aa],dfn[bb]);
            if(aa==bb)
                cout<<0<<" asd"<<'\n';
            else
                cout<<qchain(aa,bb)<<'\n';

这段代码好像有问题

by Y2y7m @ 2023-09-02 10:53:52

@quchenming

还有 qchain 中有问题

改完过了。

#include<bits/stdc++.h>
#define int long long
#define base 200807
#define mod 212370440130137903
using namespace std;
const int N=1e5+5;
int n,tot=0,cnt=0;
int head[N],dep[N],siz[N],fa[N],w[N],dfn[N],son[N],top[N],ba[N];
struct edge{
    int to,next,z,ii;
}e[N*2];
struct node{
    int l,r;
    int mx;
}a[N*4];
///////////////////////////////////////
void ade(int u,int v,int w,int sa){
    e[tot]=(edge){v,head[u],w,sa};
    head[u]=tot++;
    e[tot]=(edge){u,head[v],w,sa};
    head[v]=tot++;
    return ;
}
void dfs1(int nw,int f){
    fa[nw]=f;
    dep[nw]=dep[f]+1;
    siz[nw]=1;
    int asd=-1;
    for(int i=head[nw];~i;i=e[i].next){
        int er=e[i].to;
        if(er==f)
            continue;
        dfs1(er,nw);
        siz[nw]+=siz[er];
        if(siz[er]>asd){
            asd=siz[er];
            son[nw]=er;
        }
    }
    return ;
}
void dfs2(int nw,int t){
    dfn[nw]=++cnt;
    top[nw]=t;
    if(!son[nw])
        return ;
    dfs2(son[nw],t); 
    for(int i=head[nw];~i;i=e[i].next){
        int er=e[i].to;
        if(er==son[nw]){
            w[dfn[er]]=e[i].z;
            ba[e[i].ii]=dfn[er];
            continue;
        }
        if(er==fa[nw])
            continue;
        dfs2(er,er);
        w[dfn[er]]=e[i].z;
        ba[e[i].ii]=dfn[er];
    }
    return ;
}
///////////////////////////////////////
void push_up(int aa){
    a[aa].mx=max(a[aa*2].mx,a[aa*2+1].mx);
    return ;
}
void build(int aa,int l,int r){
    a[aa].l=l;
    a[aa].r=r;
    if(l==r){
        a[aa].mx=w[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(aa*2,l,mid);
    build(aa*2+1,mid+1,r);
    push_up(aa);
    return ;
}
void modify(int aa,int lr,int z){
    if(a[aa].l==a[aa].r){
        a[aa].mx=z;
        return ;
    }
    int mid=(a[aa].l+a[aa].r)>>1;
    if(lr<=mid)
        modify(aa*2,lr,z);
    else
        modify(aa*2+1,lr,z);
    push_up(aa);
    return ;
}
int query(int aa,int l,int r){
    if(a[aa].l>=l&&a[aa].r<=r)
        return a[aa].mx;
    int ans=-2147483647,mid=(a[aa].l+a[aa].r)>>1;
    if(l<=mid)
        ans=max(ans,query(aa*2,l,r));
    if(r>mid)
        ans=max(ans,query(aa*2+1,l,r));
    return ans;
}
///////////////////////////////////////
int qchain(int x,int y){
    int ans=-2147483647;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans=max(ans,query(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    ans=max(ans,query(1,dfn[x]+1,dfn[y]));
    return ans;
}
///////////////////////////////////////
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,h;
        cin>>u>>v>>h;
        ade(u,v,h,i);
    }
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
//  for(int i=1;i<=n;i++)
//      cout<<ba[i]<<'\n';
    while(1){
        string asd;
        int aa,bb;
        cin>>asd;
        if(asd[0]=='D')
            break;
        if(asd[0]=='C'){
            cin>>aa>>bb;
            modify(1,ba[aa],bb);
        }
        else{
            cin>>aa>>bb;
            if(aa==bb) cout<<0<<endl;
            else cout<<qchain(aa,bb)<<'\n';
        }
    }
    return 0;
}

by QCurium @ 2023-09-02 10:57:58

@Y2y7m 感谢yym大佬，%%%%%%%%%%%%

by QCurium @ 2023-09-02 11:05:32

当时脑子抽了，想着得让dfn小的在前，就写出了那坨答辩代码