好吧，是不是树剖板子做多了要挑战点难的……我们看看这道题吧！
（好吧这题其实也就比板子难那么一点，至少给国集做是太简单了(^^)）
这道题就是代码特别长，好像咋写都要到5K左右。
还是老套的树剖起手，这题其实唯一麻烦的地方在于他有一个全部取相反数的操作，这个我们可以打上一个rev标记。然后每次在下放的时候，下层的rev标记要^1,下层的权值要*-1，下层的最大最小值要先进行交换之后再*-1.然后合并答案的时候要同时维护权值，最大值和最小值。
然后这题要把边权转化为点权，常规操作，我们把根（直接设成0就行）的点权赋为0，剩下的对于每一条边的边权都赋给它下面的第一个节点即可。不过这样的话在树剖沿链上调的时候LCA是不能计算在内的，这点需要注意一下。还有就是要注意这题是从0开始的，每次在单点修改也要下放标记。
之后就没啥了……就是代码贼长还容易写错……
看一下5K的代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 200005; const int mod = 1000000007; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,x,y,z,head[M],ecnt,dfn[M],hson[M],fa[M],top[M],idx,size[M],dep[M],ch[M],rk[M],m; char s[10]; struct edge { int next,to,v; }e[M<<1]; struct seg { int v,minn,maxn,rev; }t[M<<2]; void add(int x,int y,int z) { e[++ecnt].to = y; e[ecnt].next = head[x]; e[ecnt].v = z; head[x] = ecnt; } void dfs1(int x,int f,int depth) { size[x] = 1,fa[x] = f,dep[x] = depth; int maxson = -1; for(int i = head[x];i;i = e[i].next) { if(e[i].to == f) continue; ch[e[i].to] = e[i].v; dfs1(e[i].to,x,depth+1); size[x] += size[e[i].to]; if(size[e[i].to] > maxson) maxson = size[e[i].to],hson[x] = e[i].to; } } void dfs2(int x,int t) { top[x] = t,dfn[x] = ++idx,rk[idx] = ch[x]; if(!hson[x]) return; dfs2(hson[x],t); for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa[x] || e[i].to == hson[x]) continue; dfs2(e[i].to,e[i].to); } } void update(int p) { t[p].v = t[p<<1].v + t[p<<1|1].v; t[p].maxn = max(t[p<<1].maxn,t[p<<1|1].maxn); t[p].minn = min(t[p<<1].minn,t[p<<1|1].minn); } void build(int p,int l,int r) { if(l == r) { t[p].v = t[p].minn = t[p].maxn = rk[l]; return; } int mid = (l+r) >> 1; build(p<<1,l,mid),build(p<<1|1,mid+1,r); update(p); } void pushdown(int p,int l,int r) { t[p<<1].v *= -1,t[p<<1|1].v *= -1; t[p<<1].rev ^= 1,t[p<<1|1].rev ^= 1; swap(t[p<<1].minn,t[p<<1].maxn); swap(t[p<<1|1].minn,t[p<<1|1].maxn); t[p<<1].minn *= -1,t[p<<1].maxn *= -1; t[p<<1|1].minn *= -1,t[p<<1|1].maxn *= -1; t[p].rev = 0; } void modify(int p,int l,int r,int pos,int val) { if(l == r) { t[p].v = t[p].minn = t[p].maxn = val; return; } int mid = (l+r) >> 1; if(t[p].rev) pushdown(p,l,r); if(pos <= mid) modify(p<<1,l,mid,pos,val); else modify(p<<1|1,mid+1,r,pos,val); update(p); } void rever(int p,int l,int r,int kl,int kr) { if(l == kl && r == kr) { t[p].v *= -1,t[p].rev ^= 1; swap(t[p].minn,t[p].maxn); t[p].minn *= -1,t[p].maxn *= -1; return; } int mid = (l+r) >> 1; if(t[p].rev) pushdown(p,l,r); if(kr <= mid) rever(p<<1,l,mid,kl,kr); else if(kl > mid) rever(p<<1|1,mid+1,r,kl,kr); else rever(p<<1,l,mid,kl,mid),rever(p<<1|1,mid+1,r,mid+1,kr); update(p); } int query(int p,int l,int r,int kl,int kr,int flag) { if(l == kl && r == kr) { if(flag == 1) return t[p].v; if(flag == 2) return t[p].minn; if(flag == 3) return t[p].maxn; } int mid = (l+r) >> 1; if(t[p].rev) pushdown(p,l,r); if(kr <= mid) return query(p<<1,l,mid,kl,kr,flag); else if(kl > mid) return query(p<<1|1,mid+1,r,kl,kr,flag); else { int g1 = query(p<<1,l,mid,kl,mid,flag),g2 = query(p<<1|1,mid+1,r,mid+1,kr,flag); if(flag == 1) return g1 + g2; if(flag == 2) return min(g1,g2); if(flag == 3) return max(g1,g2); } update(p); } void rrange(int x,int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); rever(1,1,n,dfn[top[x]],dfn[x]); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); if(dfn[x] == dfn[y]) return; rever(1,1,n,dfn[x]+1,dfn[y]); } int srange(int x,int y) { int ans = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); ans += query(1,1,n,dfn[top[x]],dfn[x],1); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); if(dfn[x] == dfn[y]) return ans; ans += query(1,1,n,dfn[x]+1,dfn[y],1); return ans; } int maxrange(int x,int y) { int cur = -1000000009; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); cur = max(cur,query(1,1,n,dfn[top[x]],dfn[x],3)); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); if(dfn[x] == dfn[y]) return cur; cur = max(cur,query(1,1,n,dfn[x]+1,dfn[y],3)); return cur; } int minrange(int x,int y) { int cur = 1000000009; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); cur = min(cur,query(1,1,n,dfn[top[x]],dfn[x],2)); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); if(dfn[x] == dfn[y]) return cur; cur = min(cur,query(1,1,n,dfn[x]+1,dfn[y],2)); return cur; } int main() { n = read(); rep(i,1,n-1) x = read(),y = read(),z = read(),add(x,y,z),add(y,x,z); dfs1(0,0,1),dfs2(0,0),build(1,1,n); m = read(); while(m--) { scanf("%s",s); if(s[0] == 'C') x = read(),y = read(),modify(1,1,n,dfn[x],y); else if(s[0] == 'N') x = read(),y = read(),rrange(x,y); else if(s[0] == 'S') x = read(),y = read(),printf("%d ",srange(x,y)); else if(s[1] == 'A') x = read(),y = read(),printf("%d ",maxrange(x,y)); else x = read(),y = read(),printf("%d ",minrange(x,y)); } return 0; }