何以 50 TLE?

就是标准的用线段树维护树链剖分。

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
long long read(){
    long long x=0,sgn=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*sgn;
}
void write(long long n){
    if(n<0){putchar('-');n=-n;}
    if(n>9)write(n/10);
    putchar(n%10+'0');
}
long long n,a[maxn],x,y,z;
long long kk,poi[maxn],nex[maxn],v[maxn],w[maxn];
long long f[maxn],dis[maxn],siz[maxn],h[maxn];
long long top[maxn],dfn[maxn],rnk[maxn],cnt;
struct edge{
    long long x,y;
}e[maxn];
struct node{
    long long l,r,ma;
}t[4*maxn];
char st[20];
long long k,ans;
void add_edge(long long x,long long y,long long z){
    kk++;v[kk]=y;w[kk]=z;nex[kk]=poi[x];poi[x]=kk;
}
void dfs1(long long x,long long fa){
    long long save=poi[x];
    siz[x]=1;
    while(save>0){
        if(v[save]!=fa){
            f[v[save]]=x;
            a[v[save]]=w[save];
            dis[v[save]]=dis[x]+1;
            dfs1(v[save],x);
            siz[x]+=siz[v[save]];
        }
        save=nex[save];
    }
    save=poi[x];
    while(save>0){
        if(v[save]!=fa)
            if(a[v[save]]>a[h[x]])h[x]=v[save];
        save=nex[save];
    }
}
void dfs2(long long x,long long ding){
    cnt++;dfn[x]=cnt;rnk[cnt]=x;top[x]=ding;
    if(h[x]!=0)dfs2(h[x],ding);
    long long save=poi[x];
    while(save>0){
        if(v[save]!=f[x]&&v[save]!=h[x])
            dfs2(v[save],v[save]);
        save=nex[save];
    }
}
void build(long long i,long long l,long long r){
    t[i].l=l;t[i].r=r;
    if(l==r){
        t[i].ma=a[rnk[l]];
        return;
    }
    long long mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    t[i].ma=max(t[i*2].ma,t[i*2+1].ma);
}
void chaxun(long long i,long long x,long long y){
    if(x<=t[i].r&&y>=t[i].l){
        if(x<=t[i].l&&y>=t[i].r){
            ans=max(ans,t[i].ma);
            return;
        }
        chaxun(i*2,x,y);
        chaxun(i*2+1,x,y);
    }
}
void xiugai2(long long i,long long x,long long y,long long k){
    if(x<=t[i].r&&y>=t[i].l){
        if(x<=t[i].l&&y>=t[i].r){
            //直接覆
            t[i].ma=k; 
            return; 
        }
        xiugai2(i*2,x,y,k);
        xiugai2(i*2+1,x,y,k);
        t[i].ma=max(t[i*2].ma,t[i*2+1].ma);
    }
}

int main(){
//  long long t=clock();
//  freopen("1.in","r",stdin);  
//  freopen("114.out","w",stdout); 
    n=read();
    for(int i=1;i<=n-1;i++){
        x=read();y=read();z=read();
        e[i].x=x;e[i].y=y;
        add_edge(x,y,z);
        add_edge(y,x,z);
    }

    dis[1]=1;
    dfs1(1,0);
    dfs2(1,1);
    //线段树中存储的是重新编号之后的编号 
    build(1,1,n);
    while(1){
        scanf("%s",st);
        ans=0;
        if(st[0]=='D')break;
        if(st[0]=='Q'){
            x=read();y=read();
            if(x==y){
                write(0);putchar('\n');
                continue;
            }
            while(top[x]!=top[y]){
                if(dis[top[x]]<dis[top[y]])swap(x,y);
                chaxun(1,dfn[top[x]],dfn[x]);
                x=f[top[x]];
                //cout<<x<<" "<<y<<endl;
            }
            if(dis[x]>dis[y])swap(x,y);
            chaxun(1,dfn[x]+1,dfn[y]);
            write(ans);putchar('\n');
        }
        if(st[0]=='C'){
            x=read();k=read();
            if(dis[e[x].x]>dis[e[x].y])x=e[x].x;
            else x=e[x].y;
            xiugai2(1,dfn[x],dfn[x],k);
        }
    }
    return 0;
}

快读快输什么都加上了，但还是T。我觉得复杂度没有问题啊。