参考了皎月半洒花的博客
看到树想到树剖，由于要取距自己到根离自己最近的标记点，刚开始想到线段树里存节点深度，查询时返回最大值。但是这样的话只能得到节点深度，无法得知节点编号，就想倍增乱搞一下，求出标记点，复杂度(O(log ^ {3};N))
虽然可以过但是实现有点复杂，就看了一下上面的博客
真的很强，由于树剖dfs时一条链上的编号是连续的，在此链中且深度越大线段树编号越大，所以我们可以在线段树里存当前节点的线段树编号，也达到了维护深度最大值的效果
答案就是ori [ (一条链中) MAX index] (ori为线段树编号回找树原始编号的数组)
复杂度(O(log ^ {2};N))
一直都是把树剖当板子用的，现在发现结合性质还有更多用处，我还要加油啊
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 1000019,INF = 1e9;
int num,na,nume,cnt;
int head[maxn];
struct Node{int v,nxt;}E[maxn * 2];
void add(int u,int v){
E[++nume].nxt = head[u];
E[nume].v = v;
head[u] = nume;
}
int size[maxn],wson[maxn],dep[maxn],fa[maxn],top[maxn],pos[maxn],ori[maxn];
int v[maxn];
void dfs1(int id,int F){
size[id] = 1;
for(int i = head[id];i;i = E[i].nxt){
int v = E[i].v;
if(v == F)continue;
dep[v] = dep[id] + 1;
fa[v] = id;
dfs1(v,id);
size[id] += size[v];
if(size[v] > size[wson[id]])wson[id] = v;
}
}
void dfs2(int id,int TP){
top[id] = TP;
pos[id] = ++cnt;
ori[cnt] = id;
if(!wson[id])return ;
dfs2(wson[id],TP);
for(int i = head[id];i;i = E[i].nxt){
int v = E[i].v;
if(v == fa[id] || v == wson[id])continue;
dfs2(v,v);
}
}
#define lid (id << 1)
#define rid (id << 1) | 1
struct sag_tree{
int l,r,max;
}tree[maxn << 2];
void build(int id,int l,int r){
tree[id].l = l;
tree[id].r = r;
if(l == r){
tree[id].max = 0;
return ;
}
int mid = (l + r) >> 1;
build(lid,l,mid);
build(rid,mid + 1,r);
tree[id].max = max(tree[lid].max,tree[rid].max);
}
void update(int id,int val, int l,int r){
if(tree[id].l == l && tree[id].r == r){
tree[id].max = l;
return ;
}
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)update(rid,val,l,r);
else if(mid >= r)update(lid,val,l,r);
else update(lid,val,l,mid),update(rid,val,mid + 1,r);
tree[id].max = max(tree[lid].max,tree[rid].max);
}
int query(int id,int l,int r){
if(tree[id].l == l && tree[id].r == r)return tree[id].max;
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)return query(rid,l,r);
else if(mid >= r)return query(lid,l,r);
else return max(query(lid,l,mid),query(rid,mid + 1,r));
}
void Qmax(int x, int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x, y);
ans = query(1, pos[top[x]], pos[x]);
if(ans){
printf("%d
", ori[ans]);
return ;
}
x = fa[top[x]];
}
if(dep[x] > dep[y])swap(x, y);
ans = query(1, pos[x], pos[y]);
printf("%d
", ori[ans]);
}
int main(){
num = RD();na = RD();
for(int i = 1;i <= num - 1;i++){
int u = RD(),v = RD();
add(u,v),add(v,u);
}
dep[1] = 1;
dfs1(1,-1);dfs2(1,1);
build(1,1,num);
update(1,pos[1],pos[1],pos[1]);
for(int i = 1;i <= na;i++){
char cmd;cin>>cmd;
if(cmd == 'C'){
int x = RD();
update(1,pos[x],pos[x],pos[x]);
}
else{
int x = RD();
Qmax(x,1);
}
}
return 0;
}