洛谷已A，某oj惨wa,求调

yjf1225 @ 2024-03-15 19:03:00

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
namespace akioi{
    const int N=3e5+10;
    const int INF=0x3f3f3f3f;
    int n;
    int h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
    int sz[N],maxx[N],g[N];
    int dfn[N],idx_dfn,sa[N];
    int top[N],dep[N],fa[N],hei[N];
    int Root,a[N],yjf[N];
    struct node{
        int maxx;
    }tree[4*N];

    void up(int k){
        tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
    }

    void build(int k,int l,int r){
        if(l==r){
            tree[k].maxx=dfn[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(2*k,l,mid);
        build(2*k+1,mid+1,r);
        up(k);
    }

    int query(int k,int l,int r,int L,int R){
        if(r<L || R<l) return 0;
        if(L<=l && r<=R){
            return tree[k].maxx;
        }
        int mid=(l+r)>>1;
        return max(query(2*k,l,mid,L,R),query(2*k+1,mid+1,r,L,R));
    }

    void modify(int k,int l,int r,int L,int d){
        if(r<L || L<l) return ;
        if(l==r){
            tree[k].maxx=d;
            return ;
        }
        int mid=(l+r)>>1;
        modify(2*k,l,mid,L,d);
        modify(2*k+1,mid+1,r,L,d);
        up(k);
    }

    void add(int x,int y,int z,int k){
        e[++idx]=y;
        w[idx]=z;
        o[idx]=k;
        ne[idx]=h[x];
        h[x]=idx;
    }

    void dfs1(int u,int de,int last){
        yjf[u]=last;
        sz[u]=1;
        for(int i=h[u];i!=-1;i=ne[i]){
            if(last==o[i]) continue;
            dep[o[i]]=de;
            dfs1(e[i],de+1,o[i]);
            sz[u]+=sz[e[i]];
            fa[o[i]]=last;
            if(sz[e[i]]>=maxx[u]){
                maxx[u]=sz[e[i]];
                g[u]=i;
            }
        }
    }

    void dfs2(int u,int tp,int last){
//      cout<<u<<' '<<last<<'\n';

        if(g[u]!=0){
            dfn[++idx_dfn]=w[g[u]];
            sa[o[g[u]]]=idx_dfn;
            top[o[g[u]]]=tp;
            dfs2(e[g[u]],tp,o[g[u]]);
        }
        for(int i=h[u];i!=-1;i=ne[i]){
            if(o[i]!=last && i!=g[u]){
                dfn[++idx_dfn]=w[i];
                top[o[i]]=o[i];
                sa[o[i]]=idx_dfn;
                dfs2(e[i],o[i],o[i]);
            }
        }
    }

    int query_lca(int x,int y){
        int ans=0;
        while(top[x]!=top[y]){
//          cout<<"!!!";
            if(dep[top[x]]>dep[top[y]]){
                ans=max(query(1,1,n,sa[top[x]],sa[x]),ans);
//              cout<<"DDD"<<sa[top[x]]<<' '<<sa[x]<<'\n';
                x=fa[top[x]];
            }
            else{
                ans=max(query(1,1,n,sa[top[y]],sa[y]),ans);
//              cout<<"DDD"<<sa[top[y]]<<' '<<sa[y]<<'\n';
                y=fa[top[y]];
            }
        }
        if(dep[x]>dep[y]){
            ans=max(ans,query(1,1,n,sa[y]+1,sa[x]));
//          cout<<sa[y]+1<<' '<<sa[x]<<'\n';
        }
        else{
            ans=max(ans,query(1,1,n,sa[x]+1,sa[y]));
//          cout<<x<<' '<<y<<' '<<sa[x]+1<<' '<<sa[y]<<'\n';
        }
        return ans;
    }

    int main(){
        memset(h,-1,sizeof(h));
        scanf("%d",&n);
        int x,y,z;
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z,i);
            add(y,x,z,i);
//          if(z==0) return 0;
        }
        dfn[++idx_dfn]=0;
        sa[0]=1;
        dfs1(1,1,0);
//      cout<<"!!!";
        dfs2(1,1,0);
        build(1,1,n);
//        for(int i=1;i<=n;i++){
//          cout<<fa[i]<<'\n';
//      }
        char op[10];
        for(int i=1;i;i++){
            scanf("%s",op);
            if(op[0]=='C'){
                cin>>x>>y;
                modify(1,1,n,sa[x],y);
            }
            else if(op[0]=='Q'){
                cin>>x>>y;
                if(x==y) printf("0\n");
                else{
//                  cout<<yjf[x]<<' '<<yjf[y]<<'\n';
                    int tmp=query_lca(yjf[x],yjf[y]);
                    printf("%d\n",tmp);
                }
            }
            else{
                break;
            }
        }
        return 0;
    }
}
signed main(){
    return akioi::main();
}
/*
5 1
1 2 1
2 3 100
3 4 2
1 5 3
1 5 2
*/

by Enoch006 @ 2024-03-15 20:50:13

@yjf1225 bsoj上你真的是这份代码吗

by lcbridge @ 2024-03-15 20:53:00

@yjf1225 我好像看出错误了

by yjf1225 @ 2024-03-15 20:53:05

@Enoch006 bsoj上题目有点不一样，是下面这份代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
namespace akioi{
    const long long N=1e6+10;
    const long long INF=0x3f3f3f3f;
    long long n;
    long long h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
    long long sz[N],maxx[N],g[N];
    long long dfn[N],idx_dfn,sa[N];
    long long top[N],dep[N],fa[N],hei[N];
    long long Root,a[N],yjf[N];
    struct node{
        long long maxx;
    }tree[4*N];

    void up(long long k){
        tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
    }

    void build(long long k,long long l,long long r){
        if(l==r){
            tree[k].maxx=dfn[l];
            return ;
        }
        long long mid=(l+r)>>1;
        build(2*k,l,mid);
        build(2*k+1,mid+1,r);
        up(k);
    }

    long long query(long long k,long long l,long long r,long long L,long long R){
        if(r<L || R<l) return 0;
        if(L<=l && r<=R){
            return tree[k].maxx;
        }
        long long mid=(l+r)>>1;
        return max(query(2*k,l,mid,L,R),query(2*k+1,mid+1,r,L,R));
    }

    void modify(long long k,long long l,long long r,long long L,long long d){
        if(r<L || L<l) return ;
        if(l==r){
            tree[k].maxx=d;
            return ;
        }
        long long mid=(l+r)>>1;
        modify(2*k,l,mid,L,d);
        modify(2*k+1,mid+1,r,L,d);
        up(k);
    }

    void add(long long x,long long y,long long z,long long k){
        e[++idx]=y;
        w[idx]=z;
        o[idx]=k;
        ne[idx]=h[x];
        h[x]=idx;
    }

    void dfs1(long long u,long long de,long long last){
        yjf[u]=last;
        sz[u]=1;
        for(long long i=h[u];i!=-1;i=ne[i]){
            if(last==o[i]) continue;
            dep[o[i]]=de;
            dfs1(e[i],de+1,o[i]);
            sz[u]+=sz[e[i]];
            fa[o[i]]=last;
            if(sz[e[i]]>=maxx[u]){
                maxx[u]=sz[e[i]];
                g[u]=i;
            }
        }
    }

    void dfs2(long long u,long long tp,long long last){
//      cout<<u<<' '<<last<<'\n';

        if(g[u]!=0){
            dfn[++idx_dfn]=w[g[u]];
            sa[o[g[u]]]=idx_dfn;
            top[o[g[u]]]=tp;
            dfs2(e[g[u]],tp,o[g[u]]);
        }
        for(long long i=h[u];i!=-1;i=ne[i]){
            if(o[i]!=last && i!=g[u]){
                dfn[++idx_dfn]=w[i];
                top[o[i]]=o[i];
                sa[o[i]]=idx_dfn;
                dfs2(e[i],o[i],o[i]);
            }
        }
    }

    long long query_lca(long long x,long long y){
        long long ans=0;
        while(top[x]!=top[y]){
//          cout<<"!!!";
            if(dep[top[x]]>dep[top[y]]){
                ans=max(query(1,1,n,sa[top[x]],sa[x]),ans);
//              cout<<"DDD"<<sa[top[x]]<<' '<<sa[x]<<'\n';
                x=fa[top[x]];
            }
            else{
                ans=max(query(1,1,n,sa[top[y]],sa[y]),ans);
//              cout<<"DDD"<<sa[top[y]]<<' '<<sa[y]<<'\n';
                y=fa[top[y]];
            }
        }
        if(dep[x]>dep[y]){
            ans=max(ans,query(1,1,n,sa[y]+1,sa[x]));
//          cout<<sa[y]+1<<' '<<sa[x]<<'\n';
        }
        else{
            ans=max(ans,query(1,1,n,sa[x]+1,sa[y]));
//          cout<<x<<' '<<y<<' '<<sa[x]+1<<' '<<sa[y]<<'\n';
        }
        return ans;
    }

    long long main(){
        memset(h,-1,sizeof(h));
        long long m;
        scanf("%lld%lld",&n,&m);
        long long x,y,z;
        for(long long i=1;i<n;i++){
            scanf("%lld%lld%lld",&x,&y,&z);
            z++;
            add(x,y,z,i);
            add(y,x,z,i);
//          if(z==0) return 0;
        }
        dfn[++idx_dfn]=0;
        sa[0]=1;
        dfs1(1,1,0);
//      cout<<"!!!";
        dfs2(1,1,0);
        build(1,1,n);
//        for(long long i=1;i<=n;i++){
//          cout<<fa[i]<<'\n';
//      }
        long long op;
        for(long long i=1;i<=m;i++){
            scanf("%lld%lld%lld",&op,&x,&y);
            if(op==0){
                modify(1,1,n,sa[x],y+1);
            }
            else{
                if(x==y || n==1) printf("-1\n");
                else{
//                  cout<<yjf[x]<<' '<<yjf[y]<<'\n';
                    long long tmp=query_lca(yjf[x],yjf[y]);
                    printf("%lld\n",tmp-1);
                }
            }
        }
        return 0;
    }
}
signed main(){
    return akioi::main();
}
/*
5 1
1 2 1
2 3 100
3 4 2
1 5 3
1 5 2
*/

by lcbridge @ 2024-03-15 20:53:25

@yjf1225 你问Enoch006

by yjf1225 @ 2024-03-15 20:53:45

@lcbridge 什么？

by yjf1225 @ 2024-03-15 20:55:50

@Enoch006 请问我的代码有什么错误？

by Enoch006 @ 2024-03-15 20:58:25

@yjf1225 有一个点是sa[y]+1有可能大于a[x]

by Enoch006 @ 2024-03-15 20:58:58

@yjf1225 改了过后bsoj上有20分了/kk

by yjf1225 @ 2024-03-15 21:00:14

@Enoch006 请问那该如何改呢？

by yjf1225 @ 2024-03-15 21:00:47

@Enoch006 我之前就有20分了