记录编号	585365	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.962 s
提交时间	2023-12-06 21:54:07	内存使用	11.49 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n;
struct made{
    int ver,nx,ed;
}e[N<<1];
int hd[N],tot,cnt;
int fa[N],size[N],dep[N],son[N];
int a[N],dfn[N],rnk[N],top[N];
struct Tree{
    int l,r,ma,la,mi;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define la(x) t[x].la 
    #define ma(x) t[x].ma
    #define mi(x) t[x].mi
}t[N<<3];
void pushup(int x){
    ma(x) = max(ma(x<<1),ma(x<<1|1));
    mi(x) = min(mi(x<<1),mi(x<<1|1));
}
void pushdown(int x){
    if(!la(x))return;
    la(x<<1) ^= 1;la(x<<1|1) ^= 1;
    ma(x<<1) *= -1;mi(x<<1) *= -1;
    ma(x<<1|1) *= -1;mi(x<<1|1) *= -1;
    swap(ma(x<<1),mi(x<<1));
    swap(ma(x<<1|1),mi(x<<1|1));
    la(x) = 0;
}//!!!!!!!!!
void build(int x,int l,int r){
    l(x) = l,r(x) = r;la(x) = 0;
    ma(x) = -1e9,mi(x) = 1e9;
    if(l == r){mi(x) = ma(x) = a[rnk[l]];return;}
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void change(int x,int l,int z){
    if(l(x) == r(x)){
        ma(x) = mi(x) = z;
        la(x) = 0;
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)change(x<<1,l,z);
    if(l > mid)change(x<<1|1,l,z);
    pushup(x);
}
int ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return ma(x);
    pushdown(x);
    int mid = l(x) + r(x) >> 1,ans = INT_MIN;
    if(l <= mid)ans = max(ans,ask(x<<1,l,r));
    if(r > mid)ans = max(ans,ask(x<<1|1,l,r));
    return ans;
}
void chan(int x,int l,int r){
    if(l <= l(x) && r(x) <= r){
        ma(x) *= -1;mi(x) *= -1;
        swap(ma(x),mi(x));
        la(x) ^= 1;
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)chan(x<<1,l,r);
    if(r > mid)chan(x<<1|1,l,r);
    pushup(x);
}
void opp(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);
        chan(1,dfn[fx],dfn[x]);
        x = fa[fx];fx = top[x];
    }
    if(dep[x] >  dep[y])swap(x,y);
    if(x == y)return;
    chan(1,dfn[x]+1,dfn[y]);
}
int query(int x,int y){
    int fx = top[x],fy = top[y],ans = INT_MIN;
    while(fx != fy){
        if(dep[fx] < dep[fy])swap(x,y),swap(fx,fy);
        ans = max(ans,ask(1,dfn[fx],dfn[x]));
        x = fa[fx];fx = top[x];
    }
    if(dep[x] >  dep[y])swap(x,y);
    //if(x == y)return ans;
    ans = max(ans,ask(1,dfn[x]+1,dfn[y]));
    return ans;
}
//-----------------------------
void add(int x,int y,int z){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],e[tot].ed = z,hd[x] = tot;
}
int li[N];//边的映射 
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver,z = e[i].ed;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt;
    rnk[cnt] = x;
    top[x] = t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
int main(){
    freopen("maintaintree.in","r",stdin);
    freopen("maintaintree.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i < n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
        a[max(x,y)] = z,li[i] = max(x,y);
    }
    dep[1] = 1;
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    char c[10];
    while(~scanf("%s",c)){
        int x,y;
        if(c[0] == 'D')break;
        scanf("%d%d",&x,&y);
        if(c[0] == 'C')change(1,dfn[li[x]],y);
        else if(c[0] == 'N')opp(x,y);
        else printf("%d\n",query(x,y));
    }
    
    return 0;
    
}