NEGATE a,b 将a b间的线段取反，这题应该用线段树+成段更新。我成段更新写的挫了，试了暴力修改过了（数据水）。
也是简单的题目。不过要注意点和边的区别。
#include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 10010; struct node{ int to; int v; int next; }edge[MAXN*3]; int ind,pre[MAXN],top[MAXN],fa[MAXN],siz[MAXN],son[MAXN],w[MAXN],deq[MAXN],fn; int n,tree[MAXN<<2],val[MAXN][3],mark[MAXN<<2]; void add(int x,int y,int z) { edge[ind].to = y; edge[ind].v = z; edge[ind].next = pre[x]; pre[x] = ind++; } void dfs1(int rt,int pa,int d) { deq[rt] = d; siz[rt] = 1; fa[rt] = pa; son[rt] = 0; for(int i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt]){ dfs1(t,rt,d+1); siz[rt] += siz[t]; if(siz[son[rt]] < siz[t]){ son[rt] = t; } } } } void dfs2(int rt,int tp) { top[rt] = tp; w[rt] = ++fn; if(son[rt] != 0){ dfs2(son[rt],tp); } for(int i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt] && t != son[rt]){ dfs2(t,t); } } } void pushup(int rt) { tree[rt] = max(tree[rt<<1],tree[rt<<1|1]); } /*void pushdown(int rt) { if(mark[rt] != 0){ if(mark[rt]%2){ tree[rt<<1] *= -1; tree[rt<<1|1] *= -1; } mark[rt<<1] += mark[rt]; mark[rt<<1|1] += mark[rt]; mark[rt] = 0; } }*/ void updata(int p,int v,int l,int r,int rt) { if(l == r){ tree[rt] = v; return ; } int m = (l+r)/2; if(m >= p){ updata(p,v,lson); } else { updata(p,v,rson); } pushup(rt); } void seg_updata(int L,int R,int l,int r,int rt) { if(l == r){ tree[rt] *= -1; return ; } int m = (l+r)/2; if(m >= L){ seg_updata(L,R,lson); } if(m < R){ seg_updata(L,R,rson); } pushup(rt); } void updata_all(int x,int y) { while(top[x] != top[y]) { if(deq[top[x]] < deq[top[y]]){ swap(x,y); } seg_updata(w[top[x]],w[x],1,fn,1); x = fa[top[x]]; } if(x == y){ return ; } if(deq[x] < deq[y]){ swap(x,y); } seg_updata(w[son[y]],w[x],1,fn,1); } int query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R){ return tree[rt]; } int m = (l+r)/2; int ans = -INF; if(m >= L){ ans = max(ans,query(L,R,lson)); } if(m < R){ ans = max(ans,query(L,R,rson)); } return ans; } int lca(int x,int y) { int ans = -INF; while(top[x] != top[y]) { if(deq[top[x]] < deq[top[y]]){ swap(x,y); } ans = max(ans,query(w[top[x]],w[x],1,fn,1)); x = fa[top[x]]; } if(x == y) return ans; if(deq[x] < deq[y]){ swap(x,y); } ans = max(ans,query(w[son[y]],w[x],1,fn,1)); return ans; } int main() { int t,i,j; scanf("%d",&t); while(t--) { ind = 1; memset(pre,-1,sizeof(pre)); scanf("%d",&n); for(i=1; i<n; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); val[i][0] = x; val[i][1] = y; val[i][2] = z; } dfs1(1,1,1); fn = 0; dfs2(1,1); for(i=1; i<n; i++){ if(deq[val[i][0]] < deq[val[i][1]]){ swap(val[i][0],val[i][1]); } updata(w[val[i][0]],val[i][2],1,fn,1); } char s[10]; memset(mark,0,sizeof(mark)); while(1) { scanf("%s",s); if(s[0] == 'D') break; if(s[0] == 'C'){ int x,y; scanf("%d%d",&x,&y); updata(w[val[x][0]],y,1,fn,1); } else if(s[0] == 'N'){ int x,y; scanf("%d%d",&x,&y); updata_all(x,y); } else { int x,y; scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } } } }