$\LARGE{思路}$
可以看出小 $A$ 取得数中, $w_x$ 一定为路径上严格次大边权, $w_y$ 为路径上最大边权。
所以小 $A$ 的决策可以用简单的树剖得出。
同理,小 $B$ 的决策为 树上 剩余的边中严格次大边权,由于是对于整棵树,所以用 $\textrm{multiset}$ 维护。
先把所有数加入 $\textrm{multiset}$ ,查询时将小 $A$ 选的从集合中暂时删除,求次大直即可。
$\LARGE{实现}$
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int a[N];
int h[N], e[N], ne[N], idx;
int dep[N], p[N], sz[N], son[N], id[N], top[N], tot;
struct Node {
int l, r, maxn, max2;
} tr[N << 2];
void Update(int &maxn, int &max2, int x) {
if (x > maxn) max2 = maxn, maxn = x;
else if (x > max2 && x < maxn) max2 = x;
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void pushup(int u) {
tr[u].maxn = -1e9, tr[u].max2 = -1e9;
Update(tr[u].maxn, tr[u].max2, tr[u << 1].maxn);
Update(tr[u].maxn, tr[u].max2, tr[u << 1].max2);
Update(tr[u].maxn, tr[u].max2, tr[u << 1 | 1].maxn);
Update(tr[u].maxn, tr[u].max2, tr[u << 1 | 1].max2);
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
tr[u].maxn = -1e9, tr[u].max2 = -1e9;
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void change(int u, int x, int k) {
if (tr[u].l == tr[u].r) {
tr[u].maxn = k, tr[u].max2 = -1e9;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) change(u << 1, x, k);
else change(u << 1 | 1, x, k);
pushup(u);
}
pair<int, int> query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r)
return {tr[u].maxn, tr[u].max2};
int mid = tr[u].l + tr[u].r >> 1;
int maxn = -1e9, max2 = -1e9;
if (l <= mid) {
auto g = query(u << 1, l, r);
Update(maxn, max2, g.first);
Update(maxn, max2, g.second);
}
if (r > mid) {
auto g = query(u << 1 | 1, l, r);
Update(maxn, max2, g.first);
Update(maxn, max2, g.second);
}
return {maxn, max2};
}
void dfs1(int u, int fa) {
sz[u] = 1, p[u] = fa, dep[u] = dep[fa] + 1;
for (int i = h[u]; ~i; i = ne[i]) {
int ver = e[i];
if (ver == fa) continue;
dfs1(ver, u);
sz[u] += sz[ver];
if (sz[ver] > sz[son[u]]) son[u] = ver;
}
}
void dfs2(int u, int topf) {
id[u] = ++ tot, top[u] = topf;
if (son[u]) dfs2(son[u], topf);
for (int i = h[u]; ~i; i = ne[i]) {
int ver = e[i];
if (ver == p[u] || ver == son[u]) continue;
dfs2(ver, ver);
}
}
int main() {
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs1(1, -1), dfs2(1, 1);
build(1, 1, tot);
multiset<int> s;
for (int i = 1; i <= n; i ++ ) {
int x;
scanf("%d", &x);
a[i] = x;
change(1, id[i], a[i]);
s.insert(a[i]);
}
scanf("%d", &m);
for (int i = 0; i < m; i ++ ) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op == 0) {
s.erase(s.find(a[x]));
a[x] += y;
s.insert(a[x]);
change(1, id[x], a[x]);
} else {
if (x == y) {
puts("-1");
continue;
}
int maxn = -1e9, max2 = -1e9;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
auto g = query(1, id[top[x]], id[x]);
//cout << top[x] << "->" << x <<":"<<g.first<<" "<<g.second<< endl;
Update(maxn, max2, g.first);
Update(maxn, max2, g.second);
x = p[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
auto g = query(1, id[x], id[y]);
//cout << x << "->" << y <<":"<<g.first<<" "<<g.second<<'\n';
Update(maxn, max2, g.first);
Update(maxn, max2, g.second);
if (max2 == -1e9) {
puts("-1");
continue;
}
printf("%d ", max2);
s.erase(s.find(maxn)), s.erase(s.find(max2));
printf("%d\n", *(-- s.lower_bound(*(-- s.end()))));
s.insert(maxn), s.insert(max2);
}
}
return 0;
}