求助
查看原帖
求助
654281
reclusive楼主2023/8/22 14:10

有没有大佬可以把我这份代码变成c语言的,本人是蒟蒻,不会。

#include<bits/stdc++.h>
using namespace std;
const int N=111000;
struct node{int x,y,c;}e[N];
struct edge{int x,y,c,pre;}a[2*N];int last[N],alen;
void ins(int x,int y,int c){
    alen++;a[alen]=edge{x,y,c,last[x]};last[x]=alen;
}
struct tnode{int fa,dep,son,c,tp,id;}t[N];
void dfs1(int x,int fa){
    t[x]=tnode{fa,t[fa].dep+1,0,1,0,0};
    for(int k=last[x];k;k=a[k].pre){
        int y=a[k].y;
        if(y!=fa){
            dfs1(y,x);
            t[x].c+=t[y].c;
            if(t[t[x].son].c<t[y].c)
                t[x].son=y;
        }
    }
}
int cnt,pos[N];
void dfs2(int x,int tp){
    t[x].id=++cnt;
    t[x].tp=tp;
    pos[cnt]=x;
    if(t[x].son!=0)dfs2(t[x].son,tp);
    for(int k=last[x];k;k=a[k].pre){
        int y=a[k].y;
        if(y!=t[x].son&&y!=t[x].fa)
            dfs2(y,y);
    }
}
struct trnode{int l,r,lc,rc,c;}tr[2*N];int trlen;
void merge(int now,int lc,int rc){
    tr[now].c=max(tr[lc].c,tr[rc].c);
}
void build(int l,int r){
    trlen++;int now=trlen;
    tr[now]=trnode{l,r,-1,-1,0};
    if(l==r)tr[now].c=0;
    else{
        int mid=(l+r)>>1;
        tr[now].lc=trlen+1;build(l,mid);
        tr[now].rc=trlen+1;build(mid+1,r);
        tr[now].c=0;
    }
}
void change(int now,int x,int c){
    if(tr[now].l==tr[now].r){tr[now].c=c;return;}
    int mid=(tr[now].l+tr[now].r)>>1,lc=tr[now].lc,rc=tr[now].rc;
    if(x<=mid)change(lc,x,c);
    else change(rc,x,c);
    merge(now,lc,rc);
}
int query(int now,int l,int r){
    if(tr[now].l==l&&tr[now].r==r)return tr[now].c;
    int mid=(tr[now].l+tr[now].r)>>1,lc=tr[now].lc,rc=tr[now].rc;
    if(r<=mid)return query(lc,l,r);
    else if(mid+1<=l)return query(rc,l,r);
    else return max(query(lc,l,mid),query(rc,mid+1,r));
}
int solve(int x,int y){
    int ans=0;
    while(t[x].tp!=t[y].tp){
        if(t[t[x].tp].dep>t[t[y].tp].dep)swap(x,y);
        ans=max(ans,query(1,t[t[y].tp].id,t[y].id));
        y=t[t[y].tp].fa;
    }
    if(x==y)return ans;
    if(t[x].dep>t[y].dep)swap(x,y);
    //深度浅的x是LCA(x,y)
    ans=max(ans,query(1,t[t[x].son].id,t[y].id));
    //t[x]的值是x与t[x].fa之间的边权,不在范围内,因此用t[x].son
    return ans;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        alen=1;memset(last,0,sizeof(last));
        for(int i=1;i<n;i++){
            int x,y,c;scanf("%d%d%d",&x,&y,&c);
            ins(x,y,c),ins(y,x,c);
            e[i]=node{x,y,c};
        }
        t[0]=tnode{0,0,0,0,0,0};cnt=0;
        memset(pos,0,sizeof(pos));
        dfs1(1,0),dfs2(1,1);
        trlen=0;build(1,cnt);
        for(int i=1;i<n;i++){
            if(t[e[i].x].dep>t[e[i].y].dep)swap(e[i].x,e[i].y);
            change(1,t[e[i].y].id,e[i].c);
        }
        char op[10];
        while(scanf("%s",op+1)!=EOF&&op[1]!='D'){
            int x,y,c;
            if(op[1]=='C'){
                scanf("%d%d",&x,&c);
                change(1,t[e[x].y].id,c);
            }
            else{
                scanf("%d%d",&x,&y);
                printf("%d\n",solve(x,y));
            }
        }
    }
    return 0;
}
2023/8/22 14:10
加载中...