题目大意：给你一棵树，有两个操作：
- $C\;x：$给第$x$个节点打上标记
- $Q\;x：$询问第$x$个节点的祖先中最近的打过标记的点（自己也是自己的祖先）
题解：树剖，可以维护区间或，然后若一段区间为$0$则跳过，否则在线段树上二分
卡点：二分部分多大了一个$=$，然后$MLE$
C++ Code：
#include#include #include #include #include namespace __IO { namespace R { int x, ch; inline int read() { ch = getchar(); while (isspace(ch)) ch = getchar(); for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x= x * 10 + (ch & 15); return x; } inline char readc() { ch = getchar(); while (!isalpha(ch)) ch = getchar(); return static_cast (ch); } }}using __IO::R::read;using __IO::R::readc;#define maxn 100010int head[maxn], cnt;struct Edge { int to, nxt;} e[maxn << 1];inline void add(int a, int b) { e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;}int n, m;int dfn[maxn], idx, fa[maxn], sz[maxn];int son[maxn], top[maxn], dep[maxn], ret[maxn];void dfs1(int u) { sz[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa[u]) { dep[v] = dep[u] + 1; fa[v] = u; dfs1(v); if (!son[u] || sz[v] > sz[son[u]]) son[u] = v; sz[u] += sz[v]; } }}void dfs2(int u) { dfn[u] = ++idx, ret[idx] = u; int v = son[u]; if (v) top[v] = top[u], dfs2(v); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != son[u] && v != fa[u]) { top[v] = v; dfs2(v); } }}namespace SgT { bool V[maxn << 2]; int pos, L, R; void modify(int rt, int l, int r) { V[rt] = true; if (l == r) return ; int mid = l + r >> 1; if (pos <= mid) modify(rt << 1, l, mid); else modify(rt << 1 | 1, mid + 1, r); } void modify(int __pos) { pos = __pos; modify(1, 1, n); } bool res; void query(int rt, int l, int r) { if (L <= l && R >= r) return static_cast (res |= V[rt]); int mid = l + r >> 1; if (L <= mid) query(rt << 1, l, mid); if (res) return ; if (R > mid) query(rt << 1 | 1, mid + 1, r); } bool query(int __L, int __R) { res = false; L = __L, R = __R; query(1, 1, n); return res; } int ans; void ask(int rt, int l, int r) { if (!V[rt]) return ; if (l == r) { if (!ans) ans = l; return ; } int mid = l + r >> 1; if (R > mid) ask(rt << 1 | 1, mid + 1, r); if (ans) return ; if (L <= mid) ask(rt << 1, l, mid); } int ask(int __L, int __R) { L = __L, R = __R; ans = 0; ask(1, 1, n); return ret[ans]; }}int query(int x) { while (top[x] != 1) { if (SgT::query(dfn[top[x]], dfn[x])) return SgT::ask(dfn[top[x]], dfn[x]); x = fa[top[x]]; } return SgT::ask(1, dfn[x]);}int main() { n = read(), m = read(); for (int i = 1, a, b; i < n; i++) { a = read(), b = read(); add(a, b); } dfs1(1); top[1] = 1; dfs2(1); SgT::modify(1); while (m --> 0) { char op = readc(); int x = read(); if (op == 'C') { SgT::modify(dfn[x]); } else { printf("%d\n", query(x)); } } return 0;}