Topic link: https://www.lydsy.com/JudgeOnline/problem.php?id=2157
This question gives us a boundary right, so we need to convert it into a point right.
Topic Requirements Operation:
1. Query the sum of all bridge pleasure values between u and V in scenic spots.
2. Query the maximum value of bridge pleasure between u and V in scenic spots
3. Query the Minimum Value of Bridge Pleasure between U and V in Scenic Spots
4. Bridge the pleasure value between u and V in the scenic area - 1
5. Modify the pleasure value of Bridge i to C
Thought: Because there is only one path between any two points in the city, we can regard the city as a tree, and we can use tree chain to divide the operation needed above.
Details:
1. When updating downwards, label the left and right children as XOR 1 instead of directly assigning 1.
2. When the interval value is - 1, the maintenance suml is reversed, and the maxl and min are exchanged, then the maintenance suml is reversed.
3. The so-called bridge is the edge we store with the adjacent table. Here we start with subscript 2, because the storage is undirected edge, so we only need to get the subscript of the adjacent table edge by the number of the bridge I << 1, I << 1 | 1.
(For example, the first bridge must be edge[2],edge[3]), so that we can find the corresponding points of each bridge (and then compare the DEPs on both sides, the weight of the bridge belongs to the point of greater dep th), so that we can successfully convert the edge weight to the point weight.
4. When operating between u and v, when two points u and V jump to the same heavy chain, the weight of the point with smaller depth should not be considered, because the operation is the edge weight between u and v, and the edge weight of the point with smaller depth is certainly not between u and V.
Code:
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <map>
#include <vector>
#include <set>
#include <bitset>
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define L(rt) rt << 1
#define R(rt) rt << 1 | 1
#define INF 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
static const int MAX_N = 1e5 + 5;
static const int Mod = 10007;
struct Edge {
int to, w, next;
}edge[MAX_N << 1];
int head[MAX_N]; //Chain Forward Star
int a[MAX_N];
int siz[MAX_N], son[MAX_N], top[MAX_N], fa[MAX_N], id[MAX_N], dep[MAX_N], rk[MAX_N];
int cnt, tot;
void dfs1(int u, int f, int d) { //The first time dfs got a heavy son
siz[u] = 1;
son[u] = 0;
fa[u] = f;
dep[u] = d;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == f) continue; //Do not repeat the road
a[v] = edge[i].w;
dfs1(v, u, d + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) { //Connect the heavy son to the heavy chain and the light son to the light chain.
top[u] = t;
id[u] = ++cnt;
rk[cnt] = u;
if (son[u]) dfs2(son[u], t); //Prioritize Heavy Chains
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u]) dfs2(v, v);
}
}
int getPoint(int u) { return dep[edge[u << 1].to] > dep[edge[u << 1 | 1].to] ? edge[u << 1].to : edge[u << 1 | 1].to; }
struct Node {
int l, r;
int minl, maxl, suml, tag;
}T[MAX_N << 2];
void prework() {
memset(head, 0, sizeof(head));
cnt = 0;
tot = 1;
}
void addEdge(int u, int v, int w) {
edge[++tot].to = v;
edge[tot].next = head[u];
edge[tot].w = w;
head[u] = tot;
}
void pushUp(int rt) {
T[rt].suml = T[L(rt)].suml + T[R(rt)].suml;
T[rt].maxl = max(T[L(rt)].maxl, T[R(rt)].maxl);
T[rt].minl = min(T[L(rt)].minl, T[R(rt)].minl);
}
void build(int rt, int l, int r) {
T[rt].l = l;
T[rt].r = r;
T[rt].tag = 0;
if (l == r) {
T[rt].maxl = T[rt].minl = T[rt].suml = a[rk[l]];
return;
}
int mid = l + r >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void pushNow(int rt) {
swap(T[rt].maxl, T[rt].minl);
T[rt].maxl = -T[rt].maxl;
T[rt].minl = -T[rt].minl;
T[rt].suml = -T[rt].suml;
T[rt].tag ^= 1;
}
void pushDown(int rt) {
if (T[rt].tag) {
pushNow(L(rt));
pushNow(R(rt));
T[rt].tag = 0;
}
}
void updatePoint(int rt, int pos, int c) {
if (T[rt].l == T[rt].r) {
T[rt].maxl = T[rt].minl = T[rt].suml = c;
return;
}
pushDown(rt);
int mid = T[rt].l + T[rt].r >> 1;
if (pos <= mid) updatePoint(L(rt), pos, c);
else updatePoint(R(rt), pos, c);
pushUp(rt);
}
void updateInterval(int rt, int ql, int qr) {
if (T[rt].l > qr || T[rt].r < ql) return;
if (T[rt].l >= ql && T[rt].r <= qr) {
pushNow(rt);
return;
}
pushDown(rt);
int mid = T[rt].l + T[rt].r >> 1;
if (ql <= mid) updateInterval(L(rt), ql, qr);
if (qr > mid) updateInterval(R(rt), ql, qr);
pushUp(rt);
}
int queryMax(int rt, int ql, int qr) {
if (T[rt].l > qr || T[rt].r < ql) return -INF;
if (T[rt].l >= ql && T[rt].r <= qr) return T[rt].maxl;
pushDown(rt);
int ans = -INF;
int mid = T[rt].l + T[rt].r >> 1;
if (ql <= mid) ans = max(ans, queryMax(L(rt), ql, qr));
if (qr > mid) ans = max(ans, queryMax(R(rt), ql, qr));
return ans;
}
int querySum(int rt, int ql, int qr) {
if (T[rt].l > qr || T[rt].r < ql) return 0;
if (T[rt].l >= ql && T[rt].r <= qr) return T[rt].suml;
pushDown(rt);
int mid = T[rt].l + T[rt].r >> 1;
int ans = 0;
if (ql <= mid) ans += querySum(L(rt), ql, qr);
if (qr > mid) ans += querySum(R(rt), ql, qr);
return ans;
}
int queryMin(int rt, int ql, int qr) {
if (T[rt].l > qr || T[rt].r < ql) return INF;
if (T[rt].l >= ql && T[rt].r <= qr) return T[rt].minl;
pushDown(rt);
int ans = INF;
int mid = T[rt].l + T[rt].r >> 1;
if (ql <= mid) ans = min(ans, queryMin(L(rt), ql, qr));
if (qr > mid) ans = min(ans, queryMin(R(rt), ql, qr));
return ans;
}
void updatePathVal(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
updateInterval(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
updateInterval(1, id[u] + 1, id[v]);
}
int queryPathMax(int u, int v) {
int ans = -INF;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans = max(ans, queryMax(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans = max(ans, queryMax(1, id[u] + 1, id[v]));
return ans;
}
int queryPathSum(int u, int v) {
int ans = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans += querySum(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans += querySum(1, id[u] + 1, id[v]);
return ans;
}
int queryPathMin(int u, int v) {
int ans = INF;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans = min(ans, queryMin(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans = min(ans, queryMin(1, id[u] + 1, id[v]));
return ans;
}
void mainwork(){
/*freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);*/
int n, q;
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
++u, ++v;
addEdge(u, v, w);
addEdge(v, u, w);
}
dfs1(1, 1, 1);
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &q);
while (q--) {
char opt[5];
int u, v, c;
scanf("%s%d%d", opt, &u, &v);
if (opt[0] == 'C') updatePoint(1, id[getPoint(u)], v);
else if (opt[0] == 'N') updatePathVal(u + 1, v + 1);
else if (opt[1] == 'U') printf("%d\n", queryPathSum(u + 1, v + 1));
else if (opt[1] == 'I') printf("%d\n", queryPathMin(u + 1, v + 1));
else printf("%d\n", queryPathMax(u + 1, v + 1));
}
}
int main() {
prework();
mainwork();
return 0;
}