对于RE的一些同学的提示

JYTS @ 2018-10-26 20:10:52

by kl膜法59改 @ 2018-11-01 19:11:00

@大帅哥就是ME 我要%您啊，机房巨神

by tuo3288 @ 2019-01-22 22:33:05

太NB了，我加之前所有点RE，加了之后就AC了

by fly仙 @ 2019-08-09 22:28:58

我这为啥RE啊

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=(1e5)*4+5;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct EDGE{
    int to,next,v;
}edge[N];
int head[N],tot=0,w[N],n,q;
int dep[N],top[N],seg[N],rev[M],size[N],son[N],U[N],V[N];
int Sum,maxn;
int sum[M],num[N],father[N],MAX[N];
void insert(int x,int y,int w)
{
    tot++;
    edge[tot].to=y;
    edge[tot].v=w;
    edge[tot].next=head[x];
    head[x]=tot;
}
/*----------------------------------

             ———— fly_仙 
-----------------------------------*/
void dfs1(int u,int f)
{
    size[u]=1;
    father[u]=f;
    dep[u]=dep[f]+1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=f)
        {
            num[v]=edge[i].v;
            dfs1(v,u);
            size[u]+=size[v];//往回传儿子的子节点数；
            if(size[v]>size[son[u]])  son[u]=v;//找到重儿子 
        }
    }
}
void dfs2(int u,int f)
{

    if(son[u])//有重儿子（不是根节点）（待确认） 
    {
        seg[son[u]]=++seg[0];//seg[0]就是一个计数的sum， seg【】记录的是它对应树的下标
        rev[seg[0]]=son[u];//rev【】记录的是树下标对应的我原本的编号
        top[son[u]]=top[u];//所在重路径最小层（顶部节点）
        dfs2(son[u],u); 
    } //整个是先可一条重路径来（待确认）
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!top[v])//没访问过
        {
            seg[v]=++seg[0];
            rev[seg[0]]=v;
            top[v]=v;
            dfs2(v,u);
         } 
     } 
}
void build(int k,int l,int r)
{
    int mid=l+r>>1;
    if(l==r)
    {
        MAX[k]=num[rev[l]];//跟正常建树一样赋初值
        return; 
    }
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    MAX[k]=max(MAX[k<<1],MAX[k<<1|1]); 
}
void query_max(int k,int l,int r,int L,int R)
{
    if(L>r||R<l) return;
    if(L<=l&&r<=R)
    {
        maxn=max(maxn,MAX[k]);
        return;
    }
    int mid=l+r>>1;
    if(mid>=L) query_max(k<<1,l,mid,L,R);
    if(mid+1<=R) query_max(k<<1|1,mid+1,r,L,R);
}
void change(int k,int l,int r,int V,int pos)
{
    if(pos>r||pos<l) return;
    if(l==r&&r==pos)
    {
        MAX[k]=V;
        return;
    }
    int mid=l+r>>1;
    if(mid>=pos) change(k<<1,l,mid,V,pos);
    if(mid+1<=pos) change(k<<1|1,mid+1,r,V,pos);
    MAX[k]=max(MAX[k<<1],MAX[k<<1|1]); 
}
void  ask(int x,int y)
{
        int fx=top[x],fy=top[y];
        while(fx!=fy)
        {
            if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
            query_max(1,1,seg[0],seg[fx],seg[x]);
            x=father[fx];fx=top[x];
        }
        if(seg[x]>seg[y]) swap(x,y); 
        query_max(1,1,seg[0],seg[x]+1,seg[y]); //因为dfs序保证 在一条重链上dfs序是从浅到深逐渐增加的
                            //  而lca在寻求过程中，最浅的保留的是f【Ta】和Ta的路径不在查询范围内所以加一就好 

}
int main()
{
    memset(head,-1,sizeof(head));   
    int x,y,w;
    n=read();   
    for(int i=1;i<=n-1;i++)
    {
        x=read(),y=read(),w=read();
        insert(x,y,w);
        insert(y,x,w); 
        U[i]=x,V[i]=y;
    }
    dfs1(1,0);
    seg[0]=seg[1]=top[1]=rev[1]=1;//以1开始 
    dfs2(1,0);
    build(1,1,seg[0]);
    char s[10];
    while(1) 
    {
      scanf("%s",s);
      if(s[0]=='D') break;
      x=read(),y=read();
      if(s[0]=='Q') 
      {
       if(x==y) printf("0\n");
       else {
       maxn=0;
       ask(x,y);
       printf("%d\n",maxn);
      }}
      if(s[0]=='C') 
      {
        int  u=U[x],v=V[x];
        if(u==father[v]) swap(u,v);
        change(1,1,seg[0],y,seg[u]);
      }
  }

return 0;
}