[HEOI2016/TJOI2016]树

树剖板子题。
维护区间最大值。
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cctype>
  8 #include<vector>
  9 #include<stack>
 10 #include<queue>
 11 using namespace std;
 12 #define enter puts("") 
 13 #define space putchar(' ')
 14 #define Mem(a, x) memset(a, x, sizeof(a))
 15 #define rg register
 16 typedef long long ll;
 17 typedef double db;
 18 const int INF = 0x3f3f3f3f;
 19 const db eps = 1e-8;
 20 const int maxn = 1e5 + 5;
 21 inline ll read()
 22 {
 23   ll ans = 0;
 24   char ch = getchar(), last = ' ';
 25   while(!isdigit(ch)) last = ch, ch = getchar();
 26   while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
 27   if(last == '-') ans = -ans;
 28   return ans;
 29 }
 30 inline void write(ll x)
 31 {
 32   if(x < 0) x = -x, putchar('-');
 33   if(x >= 10) write(x / 10);
 34   putchar(x % 10 + '0');
 35 }
 36 
 37 int n, q;
 38 char c[2];
 39 
 40 struct Edge
 41 {
 42   int nxt, to;
 43 }e[maxn << 1];
 44 int head[maxn], ecnt = -1;
 45 void addEdge(int x, int y)
 46 {
 47   e[++ecnt] = (Edge){head[x], y};
 48   head[x] = ecnt;
 49 }
 50 
 51 int dep[maxn], fa[maxn], siz[maxn], son[maxn];
 52 void dfs1(int now, int _f)
 53 {
 54   siz[now] = 1;
 55   for(int i = head[now], v; i != -1; i = e[i].nxt)
 56     {
 57       v = e[i].to;
 58       if(v == _f) continue;
 59       dep[v] = dep[now] + 1;
 60       fa[v] = now;
 61       dfs1(v, now);
 62       siz[now] += siz[v];
 63       if(!son[now] || siz[son[now]] < siz[v]) son[now] = v;
 64     }
 65 }
 66 int dfsx[maxn], pos[maxn], top[maxn], cnt = 0;
 67 void dfs2(int now, int _f)
 68 {
 69   dfsx[now] = ++cnt; pos[cnt] = now;
 70   if(son[now]) top[son[now]] = top[now], dfs2(son[now], now);
 71   for(int i = head[now], v; i != -1; i = e[i].nxt)
 72     {
 73       v = e[i].to;
 74       if(v == son[now] || v == _f) continue;
 75       top[v] = v;
 76       dfs2(v, now);
 77     }
 78     
 79 }
 80 
 81 bool vis[maxn];
 82 int l[maxn << 2], r[maxn << 2], dat[maxn << 2];
 83 void build(int L, int R, int now)
 84 {
 85   l[now] = L; r[now] = R;
 86   if(L == R) return;
 87   int mid = (L + R) >> 1;
 88   build(L, mid, now << 1);
 89   build(mid + 1, R, now << 1 | 1);
 90 }
 91 void update(int idx, int now)
 92 {
 93   if(l[now] == r[now]) {dat[now] = idx; return;}
 94   int mid = (l[now] + r[now]) >> 1;
 95   if(idx <= mid) update(idx, now << 1);
 96   else update(idx, now << 1 | 1);
 97   dat[now] = max(dat[now << 1], dat[now << 1 | 1]);
 98 }
 99 int query(int L, int R, int now)
100 {
101   if(!dat[now]) return -INF;
102   if(l[now] == L && r[now] == R) return dat[now];
103   int mid = (l[now] + r[now]) >> 1;
104   if(R <= mid) return query(L, R, now << 1);
105   else if(L > mid) return query(L, R, now << 1 | 1);
106   else return max(query(L, mid, now << 1), query(mid + 1, R, now << 1 | 1));
107 }
108 
109 int query_path(int x)
110 {
111   int ret = -INF;
112   while(top[x] != 1)
113     {
114       ret = max(ret, query(dfsx[top[x]], dfsx[x], 1));
115       x = fa[top[x]];
116     }
117   ret = max(ret, query(1, dfsx[x], 1));
118   return pos[ret];
119 }
120 
121 int main()
122 {
123   Mem(head, -1);
124   n = read(); q = read();
125   for(int i = 1; i < n; ++i)
126     {
127       int x = read(), y = read();
128       addEdge(x, y); addEdge(y, x);
129     }
130   dfs1(1, 0); top[1] = 1; dfs2(1, 0);
131   build(1, cnt, 1);
132   update(dfsx[1], 1); vis[1] = 1;
133   for(int i = 1; i <= q; ++i)
134     {
135       scanf("%s", c); int x = read();
136       if(c[0] == 'C')
137     {
138       if(!vis[x]) update(dfsx[x], 1), vis[x] = 1;
139     }
140       else write(query_path(x)), enter;
141     }
142   return 0;
143 }
View Code