Groceries in Meteor Town 题解

Groceries in Meteor Town

题目大意

维护一颗带权树，支持以下操作：

• 将 \([l,r]\) 内的点变为白色。

• 将 \([l,r]\) 内的点变为黑色。

• 查询点 \(x\) 到任意一个白色节点的简单路径上的最大值。

思路分析

没事干了把以前的题拿出来写题解。

看到『简单路径上的最大值』的字样首先想到 Kruskal 重构树。

我们先把这颗树的 Kruskal 重构树建出来，那么 \(x\) 到任意一个白色节点的简单路径上的最大值就等于 \(x\) 和所有白色节点的 LCA 的权值。

也就是说，我们只需要支持查询所有的白点的 LCA 就行了。

有一个结论：一堆点的 LCA 等于其中 dfs 序最小的点和 dfs 序最大的点的 LCA。

证明是容易的：

dfs 序所对应的子树区间只存在包含关系，不存在相交关系。

考虑三个点 \(a,b,c\) 的情况，不妨设 \(\text{dfn}_a <\text{dfn}_b<\text{dfn}_c\)，这三点的 LCA 对应的 dfs 序区间恰好包含 \(a,b,c\) 对应的 dfs 序区间，又因为 \(b\) 对应的 dfs 序区间位于 \(a,c\) 中间，故只要包含了 \(a,c\) 对应的区间就一定包含了 \(b\)。即 \(\text{LCA}(a,b,c)=\text{LCA}(a,c)\)。

更多点的情况类似。

那么我们只需要维护所有白色点的 dfs 序最值即最值所在位置就可以求出所有白点的 LCA，这可以用线段树简单实现。

具体的说，我们的线段树需要支持以下操作：

• 查询 dfs 序 最大 / 最小 的白点编号。

• 区间修改点的颜色。

这两个操作是容易做到的。

那么这题就做完了。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
const int N = 600600;
#define inf 0x3f3f3f3f
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)

int n, m, op, in1, in2, in3, cnt, rt;
int val[N], fat[N], siz[N], dep[N], top[N], dfn[N], son[N], fa[N];

struct Edge{
    int u, v, w;
}e[N];

struct STn{
    int minn, minp;
    int maxn, maxp;
    int tag;
};
struct ST{
    STn a[N << 2], b[N << 2];
    STn merge(STn p, STn a, STn b){
        p.minn = min(a.minn, b.minn);
        p.maxn = max(a.maxn, b.maxn);
        p.minp = (p.minn == a.minn ? a.minp : b.minp);
        p.maxp = (p.maxn == a.maxn ? a.maxp : b.maxp);
        return p;
    }
    void build(int p, int l, int r){
        if (l == r) {
            a[p].minn = a[p].maxn = dfn[l];
            a[p].minp = a[p].maxp = l;
            b[p] = a[p];
            return ;
        }
        build(ls, l, mid); build(rs, mid + 1, r);
        a[p] = merge(a[p], a[ls], a[rs]);
        b[p] = a[p];
    }
    void change_t(int p, int k){
        if (k == 0) a[p] = b[p];
        else a[p] = STn{inf, inf, -inf, -inf, 1};
    }
    void push_down(int p){
        if (a[p].tag == -1) return ;
        change_t(ls, a[p].tag);
        change_t(rs, a[p].tag);
        a[p].tag = -1;
    }
    void change(int p, int l, int r, int x, int y, int k){
        if (x <= l && r <= y) return change_t(p, k);
        push_down(p);
        if (x <= mid) change(ls, l, mid, x, y, k);
        if (y > mid) change(rs, mid + 1, r, x, y, k);
        a[p] = merge(a[p], a[ls], a[rs]);
    }
}tree;

vector <int> to[N];

int find(int x){
    return fat[x] == x ? x : fat[x] = find(fat[x]); 
}

void dfs_1(int s, int gr){
    fa[s] = gr; siz[s] = 1;
    dep[s] = dep[gr] + 1;
    for (auto v : to[s]) {
        dfs_1(v, s);
        siz[s] += siz[v];
        if (siz[son[s]] < siz[v]) son[s] = v;
    }
}

void dfs_2(int s, int tp){
    top[s] = tp; dfn[s] = ++ cnt;
    if (!son[s]) return ;
    dfs_2(son[s], tp);
    for (auto v : to[s])    
        if (v != fa[s] && v != son[s]) dfs_2(v, v);
}

int lca(int x, int y){
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}

int main(){
    scanf("%d %d", &n, &m); rt = 2 * n - 1;
    for (int i = 1; i <= 2 * n; i ++) fat[i] = i;
    for (int i = 1; i < n; i ++) {
        scanf("%d %d %d", &in1, &in2, &in3);
        e[i] = Edge{in1, in2, in3};
    }
    sort(e + 1, e + n, [](Edge a, Edge b){return a.w < b.w;});
    for (int i = 1; i < n; i ++) {
        to[i + n].push_back(find(e[i].u));
        to[i + n].push_back(find(e[i].v));
        val[i + n] = e[i].w;
        fat[find(e[i].u)] = fat[find(e[i].v)] = find(i + n);
    }
    dfs_1(rt, 0); dfs_2(rt, rt);
    tree.build(1, 1, rt);
    tree.change_t(1, 1);
    while (m --) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d %d", &in1, &in2);
            tree.change(1, 1, rt, in1, in2, 0);
        }
        if (op == 2) {
            scanf("%d %d", &in1, &in2);
            tree.change(1, 1, rt, in1, in2, 1);
        }
        if (op == 3) {
            scanf("%d", &in1);
            STn res = tree.a[1];
            if (res.minn == inf) {cout << "-1\n"; continue;}
            int l = lca(res.minp, res.maxp);
            if (in1 == l) {cout << "-1\n"; continue;}
            cout << val[lca(in1, lca(res.minp, res.maxp))] << '\n';
        }
    }
    return 0;
}