记录编号	399733	评测结果	TTTTTTTTEAAATTTAAAAT
题目名称	[HZOI 2016]tree—增强版	最终得分	35
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	23.331 s
提交时间	2017-04-27 16:45:05	内存使用	68.97 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <queue>
#include <vector>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1e6+10;
int size[MAXN], son[MAXN], deep[MAXN], fa[MAXN];
vector<int> G[MAXN];
void dfs(int u, int f, int d){
  size[u] = 1, fa[u] = f, deep[u] = d;
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i];
    if(to != f){
      dfs(to, u, d+1);
      size[u] += size[to];
      if(size[son[u]] < size[to])son[u] = to;
    }
  }
}
int dfs_tim, visit[MAXN], uvis[MAXN], top[MAXN];
void dfs(int u, int tp){
  visit[u] = ++dfs_tim;
  uvis[dfs_tim] = u;
  top[u] = tp;
  if(!son[u])return;
  dfs(son[u], tp);
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i];
    if(to != fa[u] && to != son[u])dfs(to, to);
  }
}
struct node{
  int ls, rs, maxv, maxp;
}ns[MAXN<<1];
int _nd = 1;
void pushup(node &d){
  if(d.ls){
    d.maxv = ns[d.ls].maxv;
    d.maxp = ns[d.ls].maxp;
  }
  if(d.rs && ns[d.rs].maxv >= d.maxv){
    d.maxv = ns[d.rs].maxv;
    d.maxp = ns[d.rs].maxp;
  }
}
int build(int l, int r){
  if(l > r)return 0;
  int c = _nd++;
  if(l < r){
    int m = (l+r)>>1;
    ns[c].ls = build(l, m);
    ns[c].rs = build(m+1, r);
    pushup(ns[c]);
  }else if(l == r)ns[c].maxp = l;
  return c;
}
void modify(int c, int p, int L, int R){
  if(!c)return;
  if(p == L && R == L)ns[c].maxv = 1;
  else{
    int M = (L+R)>>1;
    modify(ns[c].ls, p, L, M);
    modify(ns[c].rs, p, M+1, R);
    pushup(ns[c]);
  }
}
pair<int, int> query(int c, int l, int r, int L, int R){
  if(!c)return make_pair(0, 0);
  if(l <= L && R <= r)return make_pair(ns[c].maxv, ns[c].maxp);
  else{
    int M = (L+R)>>1; pair<int, int> res, tmp;
    if(l <= M)res = query(ns[c].ls, l, r, L, M);
    if(r > M){
      tmp = query(ns[c].rs, l, r, M+1, R);
      if(tmp.first >= res.first)res = tmp;
    }
    return res;
  }
}
int query(int u){
  int t = top[u];
  while(fa[u]){
    pair<int, int> qs = query(1, visit[t], visit[u], 1, dfs_tim);
    if(!qs.first){
      u = fa[t];
      t = top[u];
    }else{
      return uvis[qs.second];
    }
  }
  return 1;
}
int main(){
  freopen("tree++.in", "r", stdin);
  freopen("tree++.out", "w", stdout);
  int __size__ = 32<<20;
  char *__ptr__ = (char *)malloc(__size__)+__size__;
  __asm__("movl %0, %%esp\n"::"r"(__ptr__));
  int n, q; scanf("%d %d", &n, &q);
  for(int i = 1; i < n; i++){
    int u, v; scanf("%d %d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  dfs(1, 0, 0);
  dfs(1, 1);
  build(1, dfs_tim);
  modify(1, visit[1], 1, dfs_tim);
  while(q--){
    char op; int p;
    scanf(" %c %d", &op, &p);
    if(op == 'Q'){
      printf("%d\n", query(p));
    }else if(op == 'C'){
      modify(1, visit[p], 1, dfs_tim);
    }
  }
  return 0;
}