1867. [国家集训队2011]旅游(宋方睿)

【试题来源】

/*    rev标记：    只考虑对其子区间的影响：正常下放即可。    考虑对自身区间的影响：        假如当前区间没有标记 rev^=1（rev=1）下一次照常下放        假如当前区间  有标记 rev^=1（rev=0）两次取反抵消    特别注意：        rev表示其子区间是否需要取反。子区间！子区间！子区间！    那么当前加标记区间：无论是否有标记，都先翻转，再rev^=1。    这样才能保证正确性（想想为什么？） *///#include<ctime>#include<cstdio>#include<cstring>#include<iostream>#define lc k<<1#define rc k<<1|1using namespace std;const int N=1e5+5;const int M=N<<2;int n,m,dep[N],fa[N],son[N],siz[N],top[N];int dfs_cnt,w[N],pos[N],dfn[N];int b[N];int sum[M],mx[M],mn[M];bool rev[M];struct edge{int v,w,next;}e[N<<1];int tot,head[N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}void add(int x,int y,int z){    e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].w=z;e[tot].next=head[y];head[y]=tot;}void dfs(int x,int f,int d){    fa[x]=f;siz[x]=1;dep[x]=d;    for(int i=head[x];i;i=e[i].next){        if(e[i].v!=f){            w[e[i].v]=e[i].w;            b[i+1>>1]=e[i].v;            dfs(e[i].v,x,d+1);            siz[x]+=siz[e[i].v];            if(siz[son[x]]<siz[e[i].v]) son[x]=e[i].v;        }    }}void getpos(int x,int tp){    top[x]=tp;pos[x]=++dfs_cnt;dfn[dfs_cnt]=w[x];    if(!son[x]) return ;    getpos(son[x],tp);    for(int i=head[x];i;i=e[i].next){        if(e[i].v!=fa[x]&&e[i].v!=son[x]){            getpos(e[i].v,e[i].v);        }    }}inline void update(int k){    sum[k]=sum[lc]+sum[rc];    mx[k]=max(mx[lc],mx[rc]);    mn[k]=min(mn[lc],mn[rc]);}void deal(int k){    sum[k]=-sum[k];    mx[k]=-mx[k];    mn[k]=-mn[k];    swap(mx[k],mn[k]);}void pushdown(int k){    if(!rev[k]) return ;    rev[lc]^=1;rev[rc]^=1;rev[k]=0;    deal(lc);    deal(rc);}void build(int k,int l,int r){    if(l==r){        rev[k]=0;        mx[k]=mn[k]=sum[k]=dfn[l];        return ;    }    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    update(k);}void change(int k,int l,int r,int x,int v){    if(l==r){        rev[k]=0;        sum[k]=mx[k]=mn[k]=v;        return ;    }    pushdown(k);    int mid=l+r>>1;    if(x<=mid) change(lc,l,mid,x,v);    else  change(rc,mid+1,r,x,v);    update(k);}void SgtRever(int k,int l,int r,int x,int y){    if(l==x&&r==y){        rev[k]^=1;        deal(k);        return ;    }    pushdown(k);    int mid=l+r>>1;    if(y<=mid) SgtRever(lc,l,mid,x,y);    else if(x>mid) SgtRever(rc,mid+1,r,x,y);    else SgtRever(lc,l,mid,x,mid),SgtRever(rc,mid+1,r,mid+1,y);    update(k);}void rever(int x,int y){    for(;top[x]!=top[y];x=fa[top[x]]){        if(dep[top[x]]<dep[top[y]]) swap(x,y);        SgtRever(1,2,n,pos[top[x]],pos[x]);    }    if(dep[x]>dep[y]) swap(x,y);    if(pos[x]+1<=pos[y]) SgtRever(1,2,n,pos[x]+1,pos[y]);}int Q_sum(int k,int l,int r,int x,int y){    if(l==x&&r==y) return sum[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return Q_sum(lc,l,mid,x,y);    else if(x>mid) return Q_sum(rc,mid+1,r,x,y);    else return Q_sum(lc,l,mid,x,mid)+Q_sum(rc,mid+1,r,mid+1,y);}int Q_max(int k,int l,int r,int x,int y){    if(l==x&&r==y) return mx[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return Q_max(lc,l,mid,x,y);    else if(x>mid) return Q_max(rc,mid+1,r,x,y);    else return max(Q_max(lc,l,mid,x,mid),Q_max(rc,mid+1,r,mid+1,y));}int Q_min(int k,int l,int r,int x,int y){    if(l==x&&r==y) return mn[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return Q_min(lc,l,mid,x,y);    else if(x>mid) return Q_min(rc,mid+1,r,x,y);    else return min(Q_min(lc,l,mid,x,mid),Q_min(rc,mid+1,r,mid+1,y));}int find_sum(int x,int y){    int ans=0;    for(;top[x]!=top[y];x=fa[top[x]]){        if(dep[top[x]]<dep[top[y]]) swap(x,y);        ans+=Q_sum(1,2,n,pos[top[x]],pos[x]);    }    if(dep[x]>dep[y]) swap(x,y);    if(pos[x]+1<=pos[y]) ans+=Q_sum(1,2,n,pos[x]+1,pos[y]);    return ans;}int find_max(int x,int y){    int ans=-2e9;    for(;top[x]!=top[y];x=fa[top[x]]){        if(dep[top[x]]<dep[top[y]]) swap(x,y);        ans=max(ans,Q_max(1,2,n,pos[top[x]],pos[x]));    }    if(dep[x]>dep[y]) swap(x,y);    if(pos[x]+1<=pos[y]) ans=max(ans,Q_max(1,2,n,pos[x]+1,pos[y]));    return ans;}int find_min(int x,int y){    int ans=2e9;    for(;top[x]!=top[y];x=fa[top[x]]){        if(dep[top[x]]<dep[top[y]]) swap(x,y);        ans=min(ans,Q_min(1,2,n,pos[top[x]],pos[x]));    }    if(dep[x]>dep[y]) swap(x,y);    if(pos[x]+1<=pos[y]) ans=min(ans,Q_min(1,2,n,pos[x]+1,pos[y]));    return ans;}int main(){    n=read();    for(int i=1,x,y,z;i<n;i++) x=read()+1,y=read()+1,z=read(),add(x,y,z);    dfs(1,1,1);getpos(1,1);    build(1,2,n);    m=read();char s[10];    for(int i=1,x,y;i<=m;i++){        scanf("%s",s);x=read();y=read();        if(s[0]!=‘C‘) x++,y++;        if(s[0]==‘C‘) change(1,2,n,pos[b[x]],y);        if(s[0]==‘N‘) rever(x,y);        if(s[0]==‘S‘) printf("%d\n",find_sum(x,y));        if(s[1]==‘A‘) printf("%d\n",find_max(x,y));        if(s[1]==‘I‘) printf("%d\n",find_min(x,y));    }//    printf("\n%.3lf.sec\n",(double)clock()/CLOCKS_PER_SEC);    return 0;}