题面
解法
并查集的方法感觉十分精妙，见
树剖+线段树也比较简单吧维护区间的答案，合并的时候根据深度判断大小
时间复杂度：\(O(q\ log^2\ n)\)
代码
#include#define N 100010using namespace std;template void read(node &x) { x = 0; int f = 1; char c = getchar(); while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();} while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}int n, q, cnt, Time;int dfn[N], siz[N], top[N], d[N], f[N], son[N];struct Edge { int next, num;} e[N * 3];struct SegmentTree { struct Node { int l, r, mx; } t[N * 4]; void build(int k, int l, int r) { t[k] = (Node) {l, r, n + 1}; if (l == r) return; int mid = (l + r) >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r); } void update(int k) { int x = t[k << 1].mx, y = t[k << 1 | 1].mx; t[k].mx = (d[x] > d[y]) ? x : y; } void modify(int k, int x, int num) { int l = t[k].l, r = t[k].r; if (l == r) {t[k].mx = num; return;} int mid = (l + r) >> 1; if (x <= mid) modify(k << 1, x, num); else modify(k << 1 | 1, x, num); update(k); } int query(int k, int L, int R) { int l = t[k].l, r = t[k].r; if (L <= l && r <= R) return t[k].mx; int mid = (l + r) >> 1; if (R <= mid) return query(k << 1, L, R); if (L > mid) return query(k << 1 | 1, L, R); int x = query(k << 1, L, mid), y = query(k << 1 | 1, mid + 1, R); return (d[x] > d[y]) ? x : y; }} T;void add(int x, int y) { e[++cnt] = (Edge) {e[x].next, y}; e[x].next = cnt;}void dfs1(int x, int fa) { d[x] = d[fa] + 1, siz[x] = 1, f[x] = fa; for (int p = e[x].next; p; p = e[p].next) { int k = e[p].num; if (k == fa) continue; dfs1(k, x); siz[x] += siz[k]; if (siz[son[x]] < siz[k]) son[x] = k; }}void dfs2(int x, int tp) { top[x] = tp, dfn[x] = ++Time; if (!son[x]) return; dfs2(son[x], tp); for (int p = e[x].next; p; p = e[p].next) { int k = e[p].num; if (k == f[x] || k == son[x]) continue; dfs2(k, k); }}int Query(int x) { int fx = top[x]; while (fx != 1) { int tmp = T.query(1, dfn[fx], dfn[x]); if (tmp != n + 1) return tmp; x = f[fx], fx = top[x]; } return T.query(1, dfn[1], dfn[x]);}int main() { read(n), read(q); cnt = n; for (int i = 1; i < n; i++) { int x, y; read(x), read(y); add(x, y), add(y, x); } dfs1(1, 0); dfs2(1, 0); d[n + 1] = 0; T.build(1, 1, n); T.modify(1, dfn[1], 1); while (q--) { char c = getchar(); int x; while (!isalpha(c)) c = getchar(); read(x); if (c == 'C') T.modify(1, dfn[x], x); else cout << Query(x) << "\n"; } return 0;}
