题目
Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
输入格式
输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0…N − 1。接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1…N − 1。|w| <= 1000。输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。接下来有M 行，每行描述了一个操作，操作有如下五种形式： C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。 N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。 SUM u v，表示询问从景点u 到v 所获得的总愉悦度。 MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。 MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。
输出格式
对于每一个询问(操作S、MAX 和MIN)，输出答案。
输入样例
3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2
输出样例
3
2
1
-1
5
3
提示
一共有10 个数据，对于第i (1 <= i <= 10) 个数据， N = M = i * 2000。
题解
凭着对树剖的熟练度，20min打完180+行直接1A【】
学了LCT发现其实树剖的题目都可以用LCT刷刷
LCT明天补上【】
UPDATE：已补LCT
果然树剖快挺多
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 20005,maxm = 100005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
return out * flag;
}
char opt[10];
int h[maxn],ne = 0,N,M;
struct EDGE{int to,nxt,w,i;}ed[maxm];
inline void build(int u,int v,int w,int i){
ed[ne] = (EDGE){v,h[u],w,i}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v],w,i}; h[v] = ne++;
}
int fa[maxn],dep[maxn],son[maxn],V[maxn],id[maxn],P[maxn],H[maxn],top[maxn],siz[maxn];
int cnt = 0;
void dfs1(int u){
siz[u] = 1; int to;
Redge(u) if ((to = ed[k].to) != fa[u]){
dep[to] = dep[u] + 1; fa[to] = u; P[ed[k].i] = to; V[to] = ed[k].w;
dfs1(to);
siz[u] += siz[to];
if (!son[u] || siz[to] > siz[son[u]]) son[u] = to;
}
}
void dfs2(int u,int flag){
id[u] = ++cnt; H[cnt] = u; top[u] = flag ? top[fa[u]] : u; int to;
if (son[u]) dfs2(son[u],true);
Redge(u) if ((to = ed[k].to) != fa[u] && to != son[u]) dfs2(to,false);
}
int sum[4 * maxn],mx[4 * maxn],mn[4 * maxn],tag[4 * maxn],L,R;
void pup(int u){
sum[u] = sum[ls] + sum[rs];
mx[u] = max(mx[ls],mx[rs]);
mn[u] = min(mn[ls],mn[rs]);
}
void pd(int u){
if (tag[u]){
sum[ls] = -sum[ls]; sum[rs] = -sum[rs];
swap(mx[ls],mn[ls]); mx[ls] = -mx[ls]; mn[ls] = -mn[ls];
swap(mx[rs],mn[rs]); mx[rs] = -mx[rs]; mn[rs] = -mn[rs];
tag[ls] ^= 1; tag[rs] ^= 1; tag[u] ^=1;
}
}
void build(int u,int l,int r){
if (l == r){
sum[u] = mx[u] = mn[u] = V[H[l]];
return;
}
int mid = l + r >> 1;
build(ls,l,mid);
build(rs,mid + 1,r);
pup(u);
}
void modify(int u,int l,int r,int v){
if (l == r) {sum[u] = mx[u] = mn[u] = v; return;}
pd(u);
int mid = l + r >> 1;
if (mid >= L) modify(ls,l,mid,v);
else modify(rs,mid + 1,r,v);
pup(u);
}
void rever(int u,int l,int r){
if (l >= L && r <= R){
sum[u] = -sum[u];
swap(mx[u],mn[u]); mx[u] = -mx[u]; mn[u] = -mn[u];
tag[u] ^= 1;
return;
}
pd(u);
int mid = l + r >> 1;
if (mid >= L) rever(ls,l,mid);
if (mid < R) rever(rs,mid + 1,r);
pup(u);
}
int Query(int u,int l,int r){
if (l >= L && r <= R) return sum[u];
pd(u);
int mid = l + r >> 1;
if (mid >= R) return Query(ls,l,mid);
else if (mid < L) return Query(rs,mid + 1,r);
else return Query(ls,l,mid) + Query(rs,mid + 1,r);
}
int Qmin(int u,int l,int r){
if (l >= L && r <= R) return mn[u];
pd(u);
int mid = l + r >> 1;
if (mid >= R) return Qmin(ls,l,mid);
else if (mid < L) return Qmin(rs,mid + 1,r);
else return min(Qmin(ls,l,mid),Qmin(rs,mid + 1,r));
}
int Qmax(int u,int l,int r){
if (l >= L && r <= R) return mx[u];
pd(u);
int mid = l + r >> 1;
if (mid >= R) return Qmax(ls,l,mid);
else if (mid < L) return Qmax(rs,mid + 1,r);
else return max(Qmax(ls,l,mid),Qmax(rs,mid + 1,r));
}
void solve1(){
int u = P[RD()],w = RD();
L = id[u]; modify(1,1,N,w);
}
void solve2(){
int u = RD() + 1,v = RD() + 1;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u,v);
L = id[top[u]]; R = id[u];
rever(1,1,N);
u = fa[top[u]];
}
if (u == v) return;
if (dep[u] > dep[v]) swap(u,v);
L = id[u] + 1; R = id[v];
rever(1,1,N);
}
void solve3(){
int u = RD() + 1,v = RD() + 1,ans = 0;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u,v);
L = id[top[u]]; R = id[u];
ans += Query(1,1,N);
u = fa[top[u]];
}
if (u != v){
if (dep[u] > dep[v]) swap(u,v);
L = id[u] + 1; R = id[v];
ans += Query(1,1,N);
}
printf("%d\n",ans);
}
void solve4(){
int u = RD() + 1,v = RD() + 1,ans = -INF;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u,v);
L = id[top[u]]; R = id[u];
ans = max(ans,Qmax(1,1,N));
u = fa[top[u]];
}
if (u != v){
if (dep[u] > dep[v]) swap(u,v);
L = id[u] + 1; R = id[v];
ans = max(ans,Qmax(1,1,N));
}
printf("%d\n",ans);
}
void solve5(){
int u = RD() + 1,v = RD() + 1,ans = INF;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u,v);
L = id[top[u]]; R = id[u];
ans = min(ans,Qmin(1,1,N));
u = fa[top[u]];
}
if (u != v){
if (dep[u] > dep[v]) swap(u,v);
L = id[u] + 1; R = id[v];
ans = min(ans,Qmin(1,1,N));
}
printf("%d\n",ans);
}
int main(){
memset(h,-1,sizeof(h));
N = RD(); int u,v,w;
REP(i,N - 1) u = RD() + 1,v = RD() + 1,w = RD(),build(u,v,w,i);
dep[1] = 1; dfs1(1); dfs2(1,0); build(1,1,N);
M = RD();
while (M--){
scanf("%s",opt);
if (opt[0] == 'C') solve1();
else if (opt[0] == 'N') solve2();
else if (opt[0] == 'S') solve3();
else if (opt[1] == 'A') solve4();
else solve5();
}
return 0;
}
LCT：【代码短但会慢一点】
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define isrt(u) (!f[u] || (ch[f[u]][0] != u && ch[f[u]][1] != u))
#define isr(u) (ch[f[u]][1] == u)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
#define ls (ch[u][0])
#define rs (ch[u][1])
using namespace std;
const int maxn = 40005,maxm = 100005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
return out * flag;
}
int rev[maxn],Min[maxn],Max[maxn],f[maxn],ch[maxn][2],sum[maxn];
int tag[maxn],V[maxn],N,M,ed[maxn];
char opt[10];
void Rever(int u){
swap(Min[u],Max[u]); Max[u] = -Max[u]; Min[u] = -Min[u];
sum[u] = -sum[u]; V[u] = -V[u];
tag[u] ^= 1;
}
void pup(int u){
Max[u] = max(Max[ls],Max[rs]);
Min[u] = min(Min[ls],Min[rs]);
if (u > N) Max[u] = max(Max[u],V[u]);
if (u > N) Min[u] = min(Min[u],V[u]);
sum[u] = sum[ls] + sum[rs] + V[u];
}
void pd(int u){
if (rev[u]){swap(ls,rs); rev[ls] ^= 1; rev[rs] ^= 1; rev[u] ^= 1;}
if (tag[u]){
if (ls) Rever(ls);
if (rs) Rever(rs);
tag[u] = 0;
}
}
void push_down(int u){
if (!isrt(u)) push_down(f[u]);
pd(u);
}
void spin(int u){
int s = isr(u),fa = f[u];
f[u] = f[fa]; if (!isrt(fa)) ch[f[fa]][isr(fa)] = u;
ch[fa][s] = ch[u][s ^ 1]; if (ch[u][s ^ 1]) f[ch[u][s ^ 1]] = fa;
f[fa] = u; ch[u][s ^ 1] = fa;
pup(fa); pup(u);
}
void splay(int u){
for (push_down(u); !isrt(u); spin(u))
if (!isrt(f[u])) spin((isr(u) ^ isr(f[u])) ? u : f[u]);
}
void Access(int u){
for (int v = 0; u; u = f[v = u])
splay(u),ch[u][1] = v,pup(u);
}
void Make_rt(int u){
Access(u); splay(u); rev[u] ^= 1;
}
void Split(int u,int v){
Make_rt(u); Access(v); splay(v);
}
void Link(int u,int v){
Make_rt(u); f[u] = v;
}
void solve1(){
int u = ed[RD()],v = RD();
splay(u); V[u] = v; pup(u);
}
void solve2(){
int u = RD() + 1,v = RD() + 1;
Split(u,v); Rever(v);
}
void solve3(){
int u = RD() + 1,v = RD() + 1;
Split(u,v);
printf("%d\n",sum[v]);
}
void solve4(){
int u = RD() + 1,v = RD() + 1;
Split(u,v);
printf("%d\n",Max[v]);
}
void solve5(){
int u = RD() + 1,v = RD() + 1;
Split(u,v);
printf("%d\n",Min[v]);
}
int main(){
N = RD();
int u,v,w,id = N;
for (int i = 0; i <= N; i++) Max[i] = -INF,Min[i] = INF;
REP(i,N - 1){
u = RD() + 1,v = RD() + 1,w = RD();
ed[i] = ++id; V[id] = Max[id] = Min[id] = sum[id] = w;
Link(u,id); Link(v,id);
}
M = RD();
while (M--){
scanf("%s",opt);
if (opt[0] == 'C') solve1();
else if (opt[0] == 'N') solve2();
else if (opt[0] == 'S') solve3();
else if (opt[1] == 'A') solve4();
else solve5();
}
return 0;
}