题目链接
树剖练手题，想复习下树剖。
第一次提交(T)成QQC
看我
???
看了数据范围的确挺恶心的，我的复杂度是(O(Mlog^2N))的，数据范围有三段
For 1/3 of the test cases, N=5000, Q=400000.
For 1/3 of the test cases, N=10000, Q=300000.
For 1/3 of the test cases, N=100000, Q=100000.
很极限就对了。难道是我常数太大了？那也不至于只对(3)个点吧。
我看了一下，原来我求(size)的时候没有加上子树的(size)...这样就会剖出假的重链。
我加上去，再交，还是(T)成QQC。
看我
......
原来是标记(top)的时候错了。改过来就(A)了。
虽然有两个细节错误，但是没有别的错误，也就是说我树剖大致模板和线段树都是一次写对的。。
话不多说。
树剖后用线段树来维护，维护最小值，黑点的值为(dfs)序，白点的值为(INF)，每次查询找到链上的最小值即为答案。
因为从(1)到(x)是一条直链，越上的点也就是越靠近(1)的点，(dfs)序一定最小。
#include <cstdio>
#define INF 2147483647
#define re register
int s; char ch;
inline int read(){
s = 0; ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
return s;
}
inline int min(int a, int b){
return a > b ? b : a;
}
const int MAXN = 100010;
struct Edge{
int next, to;
}e[MAXN << 1];
int head[MAXN], num, n, m, a, b, w[MAXN];
inline void Add(int from, int to){
e[++num].to = to; e[num].next = head[from]; head[from] = num;
e[++num].to = from; e[num].next = head[to]; head[to] = num;
}
int dep[MAXN], size[MAXN], maxson[MAXN], top[MAXN], ID, dfn[MAXN], pos[MAXN], f[MAXN];
namespace SegTree{
#define left (now << 1)
#define right (now << 1 | 1)
int Min[MAXN << 2];
inline void pushup(int now){
Min[now] = min(Min[left], Min[right]);
}
void build(int now, int l, int r){
if(l == r){ Min[now] = INF; return; }
int mid = (l + r) >> 1;
build(left, l, mid);
build(right, mid + 1, r);
pushup(now);
}
void update(int now, int l, int r, int x){
if(l == r){ Min[now] = (w[pos[x]] ? x : INF); return; }
int mid = (l + r) >> 1;
if(x <= mid) update(left, l, mid, x);
else update(right, mid + 1, r, x);
pushup(now);
}
int query(int now, int l, int r, int wl, int wr){
if(l > wr || r < wl) return INF;
if(l >= wl && r <= wr) return Min[now];
int ans = INF, mid = (l + r) >> 1;
ans = min(ans, query(left, l, mid, wl, wr));
ans = min(ans, query(right, mid + 1, r, wl, wr));
return ans;
}
}using namespace SegTree;
void dfs1(int u, int fa){
size[u] = 1; f[u] = fa;
for(re int i = head[u]; i; i = e[i].next)
if(e[i].to != fa){
dfs1(e[i].to, u);
size[u] += size[e[i].to];
if(size[e[i].to] > size[maxson[u]])
maxson[u] = e[i].to;
}
}
void dfs2(int u, int rt){
dfn[u] = ++ID; pos[ID] = u; top[u] = rt;
if(maxson[u]) dfs2(maxson[u], rt);
for(re int i = head[u]; i; i = e[i].next)
if(e[i].to != f[u] && e[i].to != maxson[u])
dfs2(e[i].to, e[i].to);
}
inline int solve(int u){
int ans = INF;
while(top[u] != 1){
ans = min(ans, query(1, 1, n, dfn[top[u]], dfn[u]));
u = f[top[u]];
}
ans = min(ans, query(1, 1, n, dfn[1], dfn[u]));
return ans == INF ? -1 : pos[ans];
}
int main(){
n = read(); m = read();
for(re int i = 1; i < n; ++i)
Add(read(), read());
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
for(re int i = 1; i <= m; ++i){
a = read(); b = read();
if(!a){
w[b] ^= 1;
update(1, 1, n, dfn[b]);
}
else printf("%d
", solve(b));
}
return 0;
}