题目地址：SPOJ：SPOJ.com – Problem QTREE3

SPOJ QTREE系列：

• [SPOJ-QTREE]Query on a tree 题解（树链剖分）
• [SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
• [SPOJ-PT07J]Query on a tree III 题解（主席树）
• [SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
• [SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
• [SPOJ-QTREE5]Query on a tree V 题解（边分治）
• [SPOJ-QTREE6]Query on a tree VI 题解（LCT）
• [SPOJ-QTREE7]Query on a tree VII 题解（LCT）

题目描述

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. In the start, the color of any node in the tree is white.
We will ask you to perfrom some instructions of the following form:

• 0 i : change the color of the i-th node (from white to black, or from black to white);
  or
• 1 v : ask for the id of the first black node on the path from node 1 to node v. if it doesn’t exist, you may return -1 as its result.

给一棵树，初始点全是白色，操作1.更改点的颜色（白->黑，黑->白）2.求1~v路径上第一个为黑色的点，不存在输出-1。

输入输出格式

输入格式：
In the first line there are two integers N and Q.
In the next N-1 lines describe the edges in the tree: a line with two integers a b denotes an edge between a and b.
The next Q lines contain instructions “0 i” or “1 v” (1 ≤ i, v ≤ N).

输出格式：
For each “1 v” operation, write one integer representing its result.

输入输出样例

输入样例#1：

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：

-1
8
-1
2
-1

说明

There are 12 real input files.
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.

题解

线段树存一段上深度最小的黑色点的编号。直接查即可。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

int n, q, ut, vt, op;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt, col[MAXN];

inline void dfs1(int u) {
    siz[u] = 1;
    son[u] = 0;
    for(register int i = head[u]; i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(v == fa[u]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

inline void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    ptn[dfn[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(register int i = head[u]; i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int sgt[MAXN << 2];

inline void modify(int o, int l, int r, int x, int v) {
    if(l == r) {
        if(v) sgt[o] = ptn[l];
        else sgt[o] = 0;
        return;
    }
    register int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(x <= mid) modify(lch, l, mid, x, v);
    else modify(rch, mid + 1, r, x, v);
    sgt[o] = dep[sgt[lch]] < dep[sgt[rch]] ? sgt[lch] : sgt[rch];
}

inline int query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return sgt[o];
    }
    register int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    register int resl = 0, resr = 0;
    if(ll <= mid) resl = query(lch, l, mid, ll, rr);
    if(rr > mid) resr = query(rch, mid + 1, r, ll, rr);
    return dep[resl] < dep[resr] ? resl : resr;
}

inline int query(int u) {
    int tu = top[u], ans = -1, res;
    while(tu) {
        res = query(1, 1, n, dfn[tu], dfn[u]);
        if(res) ans = res;
        u = fa[tu];
        tu = top[u];
    }
    return ans;
}

inline void addedge(int u, int v) {
    gra[++tot] = Edge {v, head[u]};
    head[u] = tot;
}

int main() {
    dep[0] = INF;
    n = readint(); q = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
        addedge(vt, ut);
    }
    dfs1(1);
    dfs2(1, 1);
    while(q--) {
        op = readint();
        ut = readint();
        if(op == 0) {
            col[ut] ^= 1;
            modify(1, 1, n, dfn[ut], col[ut]);
        } else {
            printf("%d\n", query(ut));
        }
    }
    return 0;
}