注意赋值和加法的标记下传优先级.具体看代码.
CODE
#include <vector>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define ls (i<<1)
#define rs (i<<1|1)
inline void read(int &num) {
char ch; int flg=1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(num=0; isdigit(ch); num=num*10+ch-'0',ch=getchar()); num*=flg;
}
const int MAXN = 100005;
const int INF = 1e9;
int n, w[MAXN], dfn[MAXN], seq[MAXN], tmr;
int fir[MAXN], cnt, bel[MAXN]; //bel表示某条边下面是哪个点
struct edge { int to, nxt, w, i; }e[MAXN<<1];
inline void add(int u, int v, int wt, int id) {
e[cnt] = (edge){ v, fir[u], wt, id }, fir[u] = cnt++;
e[cnt] = (edge){ u, fir[v], wt, id }, fir[v] = cnt++;
}
int dep[MAXN], fa[MAXN], sz[MAXN], top[MAXN], son[MAXN];
void dfs(int u, int ff) {
dep[u] = dep[fa[u]=ff] + (sz[u]=1);
for(int v, i = fir[u]; ~i; i = e[i].nxt)
if((v=e[i].to) != fa[u]) {
w[bel[e[i].i] = v] = e[i].w, dfs(v, u), sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp; seq[dfn[u] = ++tmr] = u;
if(son[u]) dfs2(son[u], tp);
for(int v, i = fir[u]; ~i; i = e[i].nxt)
if((v=e[i].to) != son[u] && v != fa[u]) dfs2(v, v);
}
int mx[MAXN<<2], lz[MAXN<<2], c[MAXN<<2];
inline void upd(int i) { mx[i] = max(mx[ls], mx[rs]); }
inline void mt(int i) {
if(~c[i]) { //先传赋值标记
mx[ls] = mx[rs] = c[i];
lz[ls] = lz[rs] = 0;
c[ls] = c[rs] = c[i];
c[i] = -1;
}
if(lz[i]) {
mx[ls] += lz[i], mx[rs] += lz[i];
lz[ls] += lz[i], lz[rs] += lz[i];
lz[i] = 0;
}
}
void build(int i, int l, int r) {
lz[i] = 0, c[i] = -1;
if(l == r) { mx[i] = w[seq[l]]; return; }
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
upd(i);
}
void modify(int i, int l, int r, int x, int y, int val) {
if(l == x && r == y) {
mx[i] += val, lz[i] += val;
return;
}
int mid = (l + r) >> 1;
mt(i);
if(y <= mid) modify(ls, l, mid, x, y, val);
else if(x > mid) modify(rs, mid+1, r, x, y, val);
else modify(ls, l, mid, x, mid, val), modify(rs, mid+1, r, mid+1, y, val);
upd(i);
}
void cover(int i, int l, int r, int x, int y, int val) {
if(l == x && r == y) {
mx[i] = c[i] = val; lz[i] = 0;
return;
}
int mid = (l + r) >> 1;
mt(i);
if(y <= mid) cover(ls, l, mid, x, y, val);
else if(x > mid) cover(rs, mid+1, r, x, y, val);
else cover(ls, l, mid, x, mid, val), cover(rs, mid+1, r, mid+1, y, val);
upd(i);
}
int query(int i, int l, int r, int x, int y) {
if(l == x && r == y) return mx[i];
int mid = (l + r) >> 1, res = 0;
mt(i);
if(y <= mid) res = query(ls, l, mid, x, y);
else if(x > mid) res = query(rs, mid+1, r, x, y);
else res = max(query(ls, l, mid, x, mid), query(rs, mid+1, r, mid+1, y));
upd(i);
return res;
}
inline int Max(int x, int y) {
int res = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res = max(res, query(1, 1, n, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if(x == y) return res;
if(dfn[x] < dfn[y]) swap(x, y);
res = max(res, query(1, 1, n, dfn[y]+1, dfn[x]));
return res;
}
inline void Add(int x, int y, int val) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
modify(1, 1, n, dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
if(x == y) return;
if(dfn[x] < dfn[y]) swap(x, y);
modify(1, 1, n, dfn[y]+1, dfn[x], val);
}
inline void Cover(int x, int y, int val) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
cover(1, 1, n, dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
if(x == y) return;
if(dfn[x] < dfn[y]) swap(x, y);
cover(1, 1, n, dfn[y]+1, dfn[x], val);
}
int main() {
memset(fir, -1, sizeof fir);
read(n);
for(int i = 1, x, y, z; i < n; ++i)
read(x), read(y), read(z), add(x, y, z, i);
dfs(1, 0); dfs2(1, 1);
build(1, 1, n);
char s[2]; int x, y, z;
while(1) {
while(!isalpha(s[0]=getchar())); s[1] = getchar();
if(s[0] == 'S') return 0;
read(x), read(y);
if(s[0] == 'M') printf("%d\n", Max(x, y));
else if(s[0] == 'A') read(z), Add(x, y, z);
else if(s[0] == 'C' && s[1] == 'o') read(z), Cover(x, y, z);
else Cover(fa[bel[x]], bel[x], y);
}
}