https://www.lydsy.com/JudgeOnline/problem.php?id=2157
现在就是后悔，非常后悔
本来想随便拿个树剖热身，不料开了个毒瘤题。
题意：动态维护一棵树上的链最大值，最小值，和，修改的操作是一条链全部取反以及一条边单点修改
边转点是肯定要边转点的，把所有的边化成两端深度更深的那个点的权值，然后直接上树剖化成线段树
线段树就是很常规的最大小值还有和，单点修改就直接改，区间修改就打lazy标记，对于一个区间的取反操作，和直接取反，最大小值互换之后取反。
问题在于对树链u,v操作的时候,lca(u,v)这个点是不可以算进去的，因为边转点的特性这个点不属于这条树链，所以考虑对u到lca和v到lca这两条树链分别操作，这样lca这个点就是需要查询（修改）的序列的端点，在操作的时候手动 + 1把这个点忽略掉就可以。
整体感觉不难，唯一的毒瘤点在于写起来很麻烦
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; 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 * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 20010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; struct Edge{ int to,next,dis,id; }edge[maxn * 2]; int head[maxn],tot; void init(){ for(int i = 0 ; i <= N + 1; i ++) head[i] = -1; tot = 0; } void add(int u,int v,int w,int id){ edge[tot].to = v; edge[tot].id = id; edge[tot].next = head[u]; edge[tot].dis = w; head[u] = tot++; } int nw[maxn]; int Index[maxn]; int dep[maxn],top[maxn],fa[maxn],val[maxn]; int pos[maxn],size[maxn],son[maxn]; const int SP = 20; int pa[maxn][SP]; void dfs1(int t,int la){ size[t] = 1; son[t] = t; pa[t][0] = la; for(int i = 1; i < SP; i ++) pa[t][i] = pa[pa[t][i - 1]][i - 1]; int heavy = 0; for(int i = head[t]; ~i ; i = edge[i].next){ int v = edge[i].to; if(v == la) continue; dep[v] = dep[t] + 1; fa[v] = t; val[v] = edge[i].dis; Index[edge[i].id] = v; dfs1(v,t); if(size[v] > heavy){ heavy = size[v]; son[t] = v; } size[t] += size[v]; } } int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); int t = dep[u] - dep[v]; for(int i = 0 ; i < SP; i ++){ if(t & (1 << i)) u = pa[u][i]; } for(int i = SP - 1; i >= 0 ; i --){ int uu = pa[u][i],vv = pa[v][i]; if(uu != vv){ u = uu; v = vv; } } return u == v?u : pa[u][0]; } int cnt; void dfs2(int t,int la){ top[t] = la; pos[t] = ++cnt; nw[cnt] = val[t]; if(son[t] == t) return; dfs2(son[t],la); for(int i = head[t]; ~i ; i = edge[i].next){ int v = edge[i].to; if((fa[t] == v) || (v == son[t])) continue; dfs2(v,v); } } struct Tree{ int l,r; int Min,Sum,Max; int lazy; }tree[maxn << 2]; void Pushup(int t){ tree[t].Min = min(tree[t << 1].Min,tree[t << 1 | 1].Min); tree[t].Max = max(tree[t << 1].Max,tree[t << 1 | 1].Max); tree[t].Sum = tree[t << 1].Sum + tree[t << 1 | 1].Sum; } void Build(int t,int l,int r){ tree[t].l = l; tree[t].r = r; tree[t].lazy = 0; if(l == r){ tree[t].Min = tree[t].Sum = tree[t].Max = nw[l]; return; } int m = (l + r) >> 1; Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r); Pushup(t); } void change(int t){ tree[t].Sum = -tree[t].Sum; swap(tree[t].Max,tree[t].Min); tree[t].Max = -tree[t].Max; tree[t].Min = -tree[t].Min; tree[t].lazy ^= 1; } void Pushdown(int t){ if(tree[t].lazy){ change(t << 1); change(t << 1 | 1); tree[t].lazy = 0; } } void update1(int t,int p,int x){ if(tree[t].l == tree[t].r){ tree[t].Sum = tree[t].Max = tree[t].Min = x; return; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(p <= m) update1(t << 1,p,x); else update1(t << 1 | 1,p,x); Pushup(t); } void update2(int t,int l,int r){ if(l <= tree[t].l && tree[t].r <= r){ change(t); return; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(r <= m) update2(t << 1,l,r); else if(l > m) update2(t << 1 | 1,l,r); else{ update2(t << 1,l,m); update2(t << 1 | 1,m + 1,r); } Pushup(t); } int query(int t,int l,int r,int p){ if(l <= tree[t].l && tree[t].r <= r){ if(p == 1) return tree[t].Sum; else if(p == 2) return tree[t].Max; return tree[t].Min; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(r <= m) return query(t << 1,l,r,p); else if(l > m) return query(t << 1 | 1,l,r,p); else{ if(p == 1) return query(t << 1,l,m,p) + query(t << 1 | 1,m + 1,r,p); else if(p == 2) return max(query(t << 1,l,m,p),query(t << 1 | 1,m + 1,r,p)); else return min(query(t << 1,l,m,p),query(t << 1 | 1,m + 1,r,p)); } } void update(int u,int v){ while(top[u] != top[v]){ update2(1,pos[top[u]],pos[u]); u = fa[top[u]]; } if(u != v) update2(1,pos[v] + 1,pos[u]); } int query(int u,int v,int p){ int ans = 0; if(p == 2) ans = -INF; else if(p == 3) ans = INF; while(top[u] != top[v]){ int t = query(1,pos[top[u]],pos[u],p); if(p == 1) ans += t; else if(p == 2) ans = max(ans,t); else ans = min(ans,t); u = fa[top[u]]; } if(u != v){ int t = query(1,pos[v] + 1,pos[u],p); if(p == 1) ans += t; else if(p == 2) ans = max(ans,t); else ans = min(ans,t); } return ans; } int main(){ Sca(N); init(); for(int i = 1; i <= N - 1; i ++){ int u,v,w; Sca3(u,v,w); u++;v++; add(u,v,w,i); add(v,u,w,i); } int root = 1; dfs1(root,0); cnt = 0; dfs2(root,root); Build(1,1,N); Sca(M); while(M--){ char op[4]; int u,v; scanf("%s%d%d",op,&u,&v); u++;v++; int l; if(op[0] == 'C') v--,u--; else l = lca(u,v); if(op[0] == 'C'){ update1(1,pos[Index[u]],v); }else if(op[0] == 'N'){ update(u,l); update(v,l); }else if(op[0] == 'S'){ Pri(query(u,l,1) + query(v,l,1)); }else if(op[1] == 'A'){ Pri(max(query(u,l,2),query(v,l,2))); }else{ Pri(min(query(u,l,3),query(v,l,3))); } } return 0; }