P2590

80ptsTLE

纪录

代码

#include <bits/stdc++.h>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;

const int N = 3e4 + 10;
const int INF = 3e4 + 10; 

std::mt19937 rdd(383494);
struct node{
	int val, mx;
}t[N << 2];
struct edge{
	int to, nxt;
}e[N * 2];

int n, q, vt, tot;
int a[N], fa[N], h[N], wc[N], sz[N];
int top[N], dfn[N], rdfn[N], dep[N];

//Graph
inline void add(int u, int v) {
	e[++tot].to = v;
	e[tot].nxt = h[u];
	h[u] = tot;
}

//Quick Read
inline int rd() {
    int s = 0, f = 1;
    char ch = getchar();
    while ('0' > ch || ch > '9') {
		if (ch == '-') f = -1; 
		ch = getchar();
	}
    while ('0' <= ch && ch <= '9') {
		s = (s << 3) + (s << 1) + ch - 48; 
		ch = getchar();
	}
    return s * f;
}

//Segment Tree
inline void build(const int u, int l, int r) {
	if (l == r) {
		t[u].val = a[rdfn[l]];
		t[u].mx = a[rdfn[l]];
		return ;
	}
	int M = (l + r) >> 1;
	build(ls, l, M);
	build(rs, M + 1, r);
    t[u].val = t[ls].val + t[rs].val;
	t[u].mx = max(t[ls].mx, t[rs].mx);
	return ;
}
inline void modify(const int u, int p, int L, int R, int k) {
    if (L == R) {
		t[u].val = t[u].mx = k;
		return ;
	}
    int M = (L + R) >> 1;
    if (p <= M) modify(ls, p, L, M, k);
    else modify(rs, p, M + 1, R, k);
    t[u].val = t[ls].val + t[rs].val;
	t[u].mx = max(t[ls].mx, t[rs].mx);
}
inline int qsum(const int u, int l, int r, int L, int R) {
	if (l <= L && r >= R) return t[u].val;
	int M = (L + R) >> 1, sum = 0;
	if (l <= M) sum += qsum(ls, l, r, L, M);
	if (r > M) sum += qsum(rs, l, r, M + 1, R);
	return sum; 
}
inline int qmax(const int u, int l, int r, int L, int R) {
   	if (l <= L && r >= R) return t[u].mx;
	int M = (L + R) >> 1, res = -INF;
   	if (l <= M) res = max(res, qmax(ls, l, r, L, M));
	if (r > M) res = max(res, qmax(rs, l, r, M + 1, R));
	return res; 
}

//Deep First Search
inline void dfs1(int u, int fat) {
	fa[u] = fat;
	sz[u] = 1;
	dep[u] = dep[fat] + 1;
	for (int i = h[u]; i; i = e[i].nxt) {
	    int v = e[i].to;
		if (v == fat) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[u] > sz[wc[u]]) wc[u] = v;
	}
	return ;
}
inline void dfs2(int u, int tp) {
    dfn[u] = ++vt;
	rdfn[vt] = u;
	top[u] = tp;
	if (wc[u]) dfs2(wc[u], tp);
	for (int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa[u] || v == wc[u]) continue;
		dfs2(v, v);
	}
	return ;
}

//Tree Chain partitioning
inline int qpsum(int x, int y) {
	int ans = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans += qsum(1, dfn[top[x]], dfn[x], 1, n);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	return (ans + qsum(1, dfn[x], dfn[y], 1, n));
}
inline int qpmax(int x, int y) {
	int ans = -INF;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = max(ans, qmax(1, dfn[top[x]], dfn[x], 1, n));
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	return max(ans, qmax(1, dfn[x], dfn[y], 1, n));
}

namespace Rand {
	mt19937 rnd(383494);
	int tr() { return rnd();}
	int gr(int k) { return tr() % (k + 1);}
	int gr(int l, int r) { return l + gr(r - l);}
}

using namespace Rand;

int main() {
    memset(sz, 0, sizeof sz);
	n = rd();
	int r = tr() % n;
	int u, v;
	for (int i = 1; i < n; ++i) {
		u = rd(), v = rd();
		add(u, v);
		add(v, u);
	}
	for (int i = 1; i <= n; ++i) a[i] = rd();
	
	dfs1(r, 0);
	dfs2(r, r);
	build(1, 1, n);
	q = rd();
	char op[10];
	int x, y;
	while (q--) {
		scanf("%s", op);
		x = rd(), y = rd();
		if (op[1] == 'H') modify(1, dfn[x], 1, n, y);
		else if (op[1] == 'M') printf("%d\n", qpmax(x, y));
		else  printf("%d\n", qpsum(x, y));
	}
	return 0;
}