把讨论区看到的所有错误都改过了,但还是 0 pts。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
#define int long long
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l(x) + r(x)) >> 1)
const int N = 300005;
const int inf = 1e18;
struct edges{
int to, next, w, id;
};
edges edge[2 * N];
int n, m, head[N], cnt = 0, vl[N];
int fa[N], size[N], dep[N], wson[N], top[N], go[N];
int idx = 0, inseg[N], ret[N];
namespace sgtree{
struct segtree{
int l, r, sum, maxn, minn;
bool opp;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define opp(x) tree[x].opp
#define maxn(x) tree[x].maxn
#define minn(x) tree[x].minn
};
segtree tree[4 * N];
void pushup(int x){
sum(x) = sum(lc) + sum(rc);
maxn(x) = max(maxn(lc), maxn(rc));
minn(x) = min(minn(lc), minn(rc));
}
void build(int x, int l, int r){
l(x) = l; r(x) = r;
opp(x) = false;
if(l == r){
sum(x) = maxn(x) = minn(x) = vl[ret[l]];
return;
}
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(x);
}
void pushdown(int x){
if(opp(x)){
opp(lc) ^= 1;
opp(rc) ^= 1;
sum(lc) = - sum(lc);
minn(lc) = - minn(lc);
maxn(lc) = - maxn(lc);
swap(minn(lc), maxn(lc));
sum(rc) = - sum(rc);
minn(rc) = - minn(rc);
maxn(rc) = - maxn(rc);
swap(minn(rc), maxn(rc));
opp(x) = false;
}
}
void modify(int x, int l, int r, int val){
if(l <= l(x) && r(x) <= r){
if(val == inf){
opp(x) ^= 1;
sum(x) = - sum(x);
minn(x) = - minn(x);
maxn(x) = - maxn(x);
swap(minn(x), maxn(x));
}else sum(x) = minn(x) = maxn(x) = val;
return;
}
pushdown(x);
if(l <= mid) modify(lc, l, r, val);
if(r > mid) modify(rc, l, r, val);
pushup(x);
}
segtree query(int x, int l, int r){
if(l <= l(x) && r(x) <= r) return tree[x];
pushdown(x);
if(r <= mid) return query(lc, l, r);
if(l > mid) return query(rc, l, r);
segtree tmp, t1, t2;
t1 = query(lc, l, r);
t2 = query(rc, l, r);
tmp.sum = t1.sum + t2.sum;
tmp.maxn = max(t1.maxn, t2.maxn);
tmp.minn = min(t1.minn, t2.minn);
pushup(x);
return tmp;
}
};
using namespace sgtree;
namespace treediv{
void dfs(int u, int ft){
fa[u] = ft;
dep[u] = dep[ft] + 1;
size[u] = 1;
for(int i = head[u]; ~ i; i = edge[i].next){
int v = edge[i].to, w = edge[i].w, id = edge[i].id;
if(v == ft) continue;
dfs(v, u);
go[id] = v;
vl[v] = w;
size[u] += size[v];
if(size[v] > size[wson[u]]) wson[u] = v;
}
}
void predo(int u, int tp){
inseg[u] = ++ idx;
ret[idx] = u;
top[u] = tp;
if(wson[u]) predo(wson[u], tp);
for(int i = head[u]; ~ i; i = edge[i].next){
int v = edge[i].to;
if(v == fa[u] || v == wson[u]) continue;
predo(v, v);
}
}
void change(int x, int y){
if(x == y) return;
int fx = top[x], fy = top[y];
while(fx != fy){
if(dep[fx] < dep[fy]){
swap(fx, fy);
swap(x, y);
}
if(inseg[fx] <= inseg[x]) modify(1, inseg[fx], inseg[x], inf);
x = fa[fx]; fx = top[x];
}
if(dep[x] > dep[x]) swap(x, y);
if(inseg[x] + 1 <= inseg[y]) modify(1, inseg[x] + 1, inseg[y], inf);
}
int ask(int x, int y, int op){
if(x == y) return 0;
int fx = top[x], fy = top[y];
int maxn = -inf, minn = inf, sum = 0;
segtree tmp;
while(fx != fy){
if(dep[fx] < dep[fy]){
swap(fx, fy);
swap(x, y);
}
if(inseg[fx] <= inseg[x]){
tmp = query(1, inseg[fx], inseg[x]);
sum += tmp.sum;
maxn = max(maxn, tmp.maxn);
minn = min(minn, tmp.minn);
}
x = fa[fx]; fx = top[x];
}
if(dep[x] > dep[x]) swap(x, y);
if(inseg[x] + 1 <= inseg[y]){
tmp = query(1, inseg[x] + 1, inseg[y]);
sum += tmp.sum;
maxn = max(maxn, tmp.maxn);
minn = min(minn, tmp.minn);
}
if(op == 1) return sum;
else if(op == 2) return maxn;
else return minn;
}
};
using namespace treediv;
void add_edge(int u, int v, int w, int id){
edge[++ cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
edge[cnt].id = id;
head[u] = cnt;
}
signed main(){
memset(head, -1, sizeof head);
scanf("%lld", &n);
for(int i = 1; i < n; i ++){
int u, v, w;
scanf("%lld %lld %lld", &u, &v, &w);
u ++; v ++;
add_edge(u, v, w, i);
add_edge(v, u, w, i);
}
scanf("%lld", &m);
dfs(1, 0);
predo(1, 1);
build(1, 1, idx);
while(m --){
string s; cin >> s;
int d1, d2; scanf("%lld %lld", &d1, &d2);
d1 ++; d2 ++;
if(s == "C"){
d1 --; d2 --;
modify(1, inseg[go[d1]], inseg[go[d1]], d2);
}
else if(s == "N") change(d1, d2);
else if(s == "SUM") printf("%lld\n", ask(d1, d2, 1));
else if(s == "MAX") printf("%lld\n", ask(d1, d2, 2));
else printf("%d\n", ask(d1, d2, 3));
}
return 0;
}