BZOJ 4538
题意：见上。
直接树剖剖成序列问题，然后每次修改取反修改区间即可，维护线段树的每个节点上都开个堆存最大重要值，再开一个堆代表删除节点堆，取顶时两个堆对比一下就行了。
知识点：
1、灵活运用树剖模板，线段树上维护堆
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200000 + 5;
int n, Q, tot, ai[MAXN], bi[MAXN], vi[MAXN];
vector<int > G[MAXN];
int siz[MAXN], dep[MAXN], son[MAXN], top[MAXN], p[MAXN], fa[MAXN], idx;
struct node {
priority_queue<int > q, qd;
int top() {
int ret = -1;
while (!qd.empty() && q.top() == qd.top()) q.pop(), qd.pop();
if (!q.empty()) ret = q.top();
return ret;
}
void push(int x) {q.push(x);}
void pushd(int x) {qd.push(x);}
} node[MAXN * 4];
struct qj {int l, r;} B[MAXN * 4];
bool cmp(qj a, qj b) {return a.l < b.l;}
void dfs_pre(int u, int pa) {
son[u] = -1, siz[u] = 1, dep[u] = dep[pa] + 1, fa[u] = pa;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != pa) {
dfs_pre(v, u);
son[u] = son[u] == -1 ? v : (siz[v] > siz[son[u]] ? v : son[u]);
siz[u] += siz[v];
}
}
}
void dfs_top(int u, int cha) {
top[u] = cha;
p[u] = ++idx;
if (son[u] != -1) dfs_top(son[u], cha);
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v != fa[u] && v != son[u]) dfs_top(v, v);
}
}
#define M ((l + r) >> 1)
#define lc (o << 1)
#define rc (o << 1 | 1)
#define ls lc, l, M
#define rs rc, M + 1, r
void update(int o, int l, int r, int x, int y, int opt, int w) {
if (x <= l && r <= y) {
if (opt == 0) node[o].push(w);
if (opt == 1) node[o].pushd(w);
return ;
}
if (x <= M) update(ls, x, y, opt, w);
if (M < y) update(rs, x, y, opt, w);
}
int query(int o, int l, int r, int x) {
int ret = -1;
if (l <= x && x <= r) ret = node[o].top();
if(l == r) return ret;
if (x <= M) ret = max(ret, query(ls, x));
else ret = max(ret, query(rs, x));
return ret;
}
void change(int u, int v, int opt, int w) {
int x = top[u], y = top[v], tot = 0;
while (x != y) {
if (dep[x] < dep[y]) swap(x, y), swap(u, v);
B[++tot] = (qj){p[x], p[u]};
u = fa[x], x = top[u];
}
if (dep[u] < dep[v]) swap(u, v);
B[++tot] = (qj){p[v], p[u]};
sort(B + 1, B + 1 + tot, cmp);
int lst = 0;
for (int i = 1; i <= tot; ++i) {
if (lst + 1 <= B[i].l - 1) update(1, 1, n, lst + 1, B[i].l - 1, opt, w);
lst = B[i].r;
}
if (lst + 1 <= n) update(1, 1, n, lst + 1, n, opt, w);
}
void clean() {
}
int solve() {
clean();
cin >> n >> Q;
for (int u, v, i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
dfs_pre(1, 0);
dfs_top(1, 1);
while (Q--) {
++tot;
int ty; scanf("%d", &ty);
if (ty == 0) {
scanf("%d%d%d", &ai[tot], &bi[tot], &vi[tot]);
change(ai[tot], bi[tot], 0, vi[tot]);
} else if (ty == 1) {
int t; scanf("%d", &t);
change(ai[t], bi[t], 1, vi[t]);
} else if (ty == 2) {
int x; scanf("%d", &x);
printf("%d\n", query(1, 1, n, p[x]));
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
