Rockdu's Blog

题目描述

给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白

有两种操作：

0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）

1 v : 询问1到v的路径上的第一个黑点，若无，输出-1

输入输出格式

输入格式：

第一行 N，Q，表示N个点和Q个操作

第二行到第N行N-1条无向边

再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).

输出格式：

对每个1 v操作输出结果

输入输出样例

9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9

-1
8
-1
2
-1

说明

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.

树链剖分模板，我们剖分一下套一个线段树维护每一个点的深度（白点为inf），然后查询inf最小的点编号就好了（我懒用了个pair……）

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, inf = 0x7fffffff;
struct edge {
    int v, next;
}e[maxn << 1];
int head[maxn], cnt, n, a, b, c, t, f, m;
typedef pair<int, int > pii;
char s;
inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0; static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
int fa[maxn], son[maxn], size[maxn], id[maxn], d[maxn], top[maxn], idcnt, ord[maxn];
int nstu[maxn];
void dfs1(int u, int p) {
    fa[u] = p, d[u] = d[p] + 1;
    size[u] = 1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        dfs1(v, u), size[u] += size[v];
        if(size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp, id[u] = ++idcnt, ord[id[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
namespace SGT {
    pii mn[maxn << 2];
	int cnt;
    void push_up(int rt) {mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);}
    void build(int l, int r, int rt) {
        if(l == r) {mn[rt].first = inf, mn[rt].second = ord[l];return ;}
        int mid = l + r >> 1;
        build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
        push_up(rt);
    }
    void edit(int pos, int tl, int tr, int dt, int rt) {
        if(tl == tr) {mn[rt].first = dt;return ;}
        int mid = tl + tr >> 1;
        if(pos <= mid) edit(pos, tl, mid, dt, rt << 1);
        else edit(pos, mid + 1, tr, dt, rt << 1 | 1);
        push_up(rt);
    }
    pii query(int l, int r, int tl, int tr, int rt) {
        if(l == tl && r == tr) return mn[rt];
        int mid = tl + tr >> 1;
        if(r <= mid) return query(l, r, tl, mid, rt << 1);
        else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
        else return min(query(l, mid, tl, mid, rt << 1), query(mid + 1, r, mid + 1, tr, rt << 1 | 1));
    }
}
#define Q(l, r) query((l), (r), 1, n, 1)
int Gmin(int v) {
    using namespace SGT;
    pii ans(inf, -1);
    while(v) ans = min(ans, Q(id[top[v]], id[v])), v = fa[top[v]];
    return ans.second;
}
int main() {
    read(n), read(m);
    for(register int i = 1; i < n; ++i) {
        read(a), read(b);
        adde(a, b), adde(b, a);
    }
    dfs1(1, 0), dfs2(1, 1);
    SGT::build(1, n, 1);
    for(register int i = 1; i <= m; ++i) {
        read(a), read(b);
        if(a) printf("%d\n", Gmin(b));
        else {
        	if(nstu[b]) SGT::edit(id[b], 1, n, inf, 1), nstu[b] = 0;
        	else SGT::edit(id[b], 1, n, d[b], 1), nstu[b] = 1;
		}
    }
    return 0;
}