#(mathcal{color{red}{Description}})
给定一棵以(1)为根的树，有两种操作：
(C: x)给点(x)打上花标记。
(Q: x)求点(x)的最近被标记祖先（自身包括）
#(mathcal{color{red}{Solution}})
这个题……操作水的很但是我还是没能秒掉，我们考虑对于一个节点，单纯考虑线段树的话好像并不可做。那么我们先来考虑简单的，对于一个点，如果要查找一个点的最近标记祖先，那我们不断查找他和他的(top)之间的节点即可，即不断进行跳链操作。那么我们线段树维护什么信息呢？首先要满足结合律，其次(query)的结果可以直接拿来用。所以我们考虑维护一段链条上面的深度最深的被标记节点。
int qmark(int u, int v){
int ans = -1 ;
while(top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v) ;
ans = query(1, 1, N, id[top[u]], id[u]) ;
if (ans != -1) return qnq[ans] ;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v) ;
return qnq[ query(1, 1, N, id[u], id[v]) ];
}
查询的时候直接查询当前节点和根节点之间即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#define il inline
#define MAXN 400001
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define to(k) e[k].t
using namespace std ;
char pt ;
int id[MAXN], s[MAXN + 1050], qnq[MAXN];
int i, a, b, tot, N, M, cnt;
int head[MAXN], fa[MAXN], hs[MAXN], top[MAXN], dep[MAXN], sub[MAXN] ;
struct node{
int t, next ;
}e[MAXN];
il void add(int u, int v){
e[++ cnt].t = v ;
e[cnt].next = head[u] ;
head[u] = cnt ;
}
il int qr(){
int k = 0;
char c = getchar() ;
while(!isdigit(c)) c = getchar() ;
while(isdigit(c)){
k = (k << 1) + (k << 3) + c - 48 ;
c = getchar() ;
}
return k ;
}
il void p_u(int rt){
s[rt] = max(s[ls(rt)], s[rs(rt)]) ;
}
il void update(int rt, int l, int r, int ul, int ur){
if (ul <= l && ur >= r){
s[rt] = l ;
return ;
}
int mid = (l + r) >> 1 ;
if (ul <= mid) update(ls(rt), l, mid, ul, ur) ;
if (ur > mid) update(rs(rt), mid + 1, r, ul, ur) ;
p_u(rt) ;
}
il int query(int rt, int l, int r, int nl, int nr){
int res = -1 ;
if (nl <= l && nr >= r) {res = s[rt];return res ;}
int mid = (l + r) >> 1 ;
if (nl <= mid)res = max(res, query(ls(rt), l, mid, nl, nr)) ;
if (nr > mid)res = max(res, query(rs(rt), mid + 1, r, nl, nr)) ;
return res ;
}
void dfs1(int now, int f, int deep){
fa[now] = f ;
dep[now] = deep ;
int hson = -1 ;
sub[now] = 1 ;
for(int k = head[now]; k ; k = e[k].next){
if(to(k) == f) continue ;
dfs1(to(k), now, deep + 1) ;
sub[now] += sub[to(k)] ;
if(hson < sub[to(k)]) hs[now] = to(k), hson = sub[to(k)] ;
}
}
void dfs2(int now, int tp){
id[now] = ++ tot;
top[now] = tp ;
qnq[tot] = now ;
if(!hs[now]) return ;
dfs2(hs[now], tp) ;
for(int k = head[now]; k ; k = e[k].next){
if(to(k) == fa[now] || to(k) == hs[now]) continue ;
dfs2(to(k), to(k)) ;
}
}
int qmark(int u, int v){
int ans = -1 ;
while(top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v) ;
ans = query(1, 1, N, id[top[u]], id[u]) ;
if (ans != -1) return qnq[ans] ;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v) ;
return qnq[ query(1, 1, N, id[u], id[v]) ];
}
int main(){
cin >> N >> M ;
memset(s, -1, sizeof(s)) ;
for(i = 1; i < N; i ++){
a = qr(), b = qr() ;
add(a, b) ;
add(b, a) ;
}
dfs1(1, 0, 1) ;
dfs2(1, 1) ;
update(1, 1, N, 1, 1) ;
for(i = 1; i <= M; i ++){
cin >> pt ;
if (pt == 'Q'){
b = qr() ;
printf("%d
", qmark(b, 1)) ;
}
else {
a = qr() ;
update(1, 1, N, id[a], id[a]) ;
}
}
}