洛谷P4116树上操作：颜色变换与路径查询

该问题的核心在于对树结构进行高效的管理和查询。具体来说，我们使用树链剖分（Heavy-Light Decomposition, HLD）结合线段树来实现高效的操作和查询。

题目描述：

给定一棵由N个节点组成的树（N-1条边），每个节点初始为白色。需要支持以下两种操作：

• 0 i：将第i个节点的颜色反转（白变黑或黑变白）。


• 1 v：询问从根节点到第v个节点的路径上第一个遇到的黑色节点编号，如果路径上没有黑色节点，则输出-1。

输入格式：

第一行包含两个整数N和Q，分别表示节点数量和操作数量。接下来N-1行每行两个整数u和v，表示一条连接u和v的无向边。最后Q行，每行一个操作0 i或1 v。

输出格式：

对于每个1 v操作，输出结果。

解决方案：

为了高效处理这些操作，我们可以使用树链剖分（HLD）配合线段树。具体步骤如下：

1. 通过两次深度优先搜索（DFS）完成树链剖分，记录每个节点的重儿子、轻儿子、深度等信息。


2. 构建线段树，维护每个区间的黑色节点信息。若区间内存在黑色节点，则记录其位置；否则记录为-1。


3. 对于每个0 i操作，更新对应节点在链上的颜色，并在线段树中同步更新。


4. 对于每个1 v操作，通过树链剖分将路径分解成若干段，在线段树中查询每段的第一个黑色节点，并合并结果。

代码实现：

#include 
#include 
#include 
#include 
#define MAXN 100233
using namespace std;

int n, m;
int tot = 0, cnt = 0;
struct Edge {
    int nex, to;
} e[MAXN <<1];
int h[MAXN], fa[MAXN], top[MAXN], son[MAXN], dep[MAXN], siz[MAXN], id[MAXN];
int w[MAXN] = {}, ans[MAXN <<2], nid[MAXN];

inline void add(int x, int y) {
    e[++tot].to = y;
    e[tot].nex = h[x];
    h[x] = tot;
}

void dfs_first(int x, int f, int dept) {
    dep[x] = dept;
    fa[x] = f;
    siz[x] = 1;
    int maxn = -1;
    for (int i = h[x], y; i; i = e[i].nex) {
        y = e[i].to;
        if (y == f) continue;
        dfs_first(y, x, dept + 1);
        siz[x] += siz[y];
        if (siz[y] > maxn) {
            son[x] = y;
            maxn = siz[y];
        }
    }
}

void dfs_second(int x, int ft) {
    top[x] = ft;
    id[x] = ++cnt;
    nid[cnt] = x;
    if (!son[x]) return;
    dfs_second(son[x], ft);
    for (int i = h[x], y; i; i = e[i].nex) {
        y = e[i].to;
        if (y == son[x] || y == fa[x]) continue;
        dfs_second(y, y);
    }
}

#define leftson cur <<1
#define rightson cur <<1 | 1
#define mid ((l + r) >> 1)
#define push_up if (ans[leftson] != -1) { ans[cur] = ans[leftson]; return; } if (ans[rightson] != -1) { ans[cur] = ans[rightson]; return; } ans[cur] = -1

void build(int cur, int l, int r) {
    if (l == r) {
        ans[cur] = -1;
        return;
    }
    build(leftson, l, mid);
    build(rightson, mid + 1, r);
    push_up;
}

void change(int adn, int cur, int l, int r) {
    if (l == r) {
        if (ans[cur] != -1) {
            ans[cur] = -1;
            return;
        }
        ans[cur] = l;
        return;
    }
    if (adn <= mid) change(adn, leftson, l, mid);
    else change(adn, rightson, mid + 1, r);
    push_up;
}

int query(int ql, int qr, int cur, int l, int r) {
    if (ql <= l && r <= qr) {
        return ans[cur];
    }
    if (ql <= mid) {
        int ans_a = query(ql, qr, leftson, l, mid);
        if (ans_a != -1) return ans_a;
    }
    if (qr > mid) return query(ql, qr, rightson, mid + 1, r);
    return -1;
}

int query_(int x, int y) {
    int ans_a, ans_b = -1;
    while (top[x] != top[y]) {
        if (dep[top[x]]         ans_a = query(id[top[x]], id[x], 1, 1, n);
        if (ans_b == -1) ans_b = ans_a;
        else if (ans_a != -1) ans_b = min(ans_a, ans_b);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans_a = query(id[x], id[y], 1, 1, n);
    if (ans_b == -1) ans_b = ans_a;
    else if (ans_a != -1) ans_b = min(ans_a, ans_b);
    return ans_b;
}

int main() {
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 1; i         scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs_first(1, 0, 1);
    dfs_second(1, 1);
    build(1, 1, n);
    for (int i = 1, answer; i <= m; i++) {
        scanf("%d%d", &x, &y);
        if (!x) {
            change(id[y], 1, 1, n);
            continue;
        }
        answer = query_(1, y);
        if (answer == -1) printf("-1\n");
        else printf("%d\n", nid[answer]);
    }
    return 0;
}