DDOSvoid's Blog

Luogu P3250 [HNOI2016] 网络

发表于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

题目描述

https://www.luogu.com.cn/problem/P3250

简要题意：给定一棵 $n$ 个点的无根树，现在有 $m$ 个操作，操作有三种，第一种操作加入一条树上的路径 $(a,b)$ 这个路径有一个权值 $c$；第二种操作给定 $x$，删除第 $x$ 个操作所加入的路径；第三种操作给定一个点 $x$，求现在存在的路径中不考虑经过 $x$ 的路径中权值最大的路径的权值

$n\le 10^5,m\le 2\times 10^5$

Solution

注意到如果查询操作所得答案为 $t$，则表示当前存在路径中所有权值大于 $t$ 的路径都经过 $x$，换言之就是这些路径的交经过 $x$，我们考虑将操作离线，将路径按照权值排序后作为在线段树中的键值，那么我们可以用线段树维护区间路径的交，每次查询相当于在线段树上二分，时间复杂度 $O(n\log n)$，细节较多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <tuple>
#include <algorithm>
#define maxn 100010
#define maxm 200010
using namespace std;

int n, m; 

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

namespace LCA {
    int id[maxn * 2], in[maxn], cnt;
    void init() { cnt = 0; } 
    void dfs(int u, int fa) {
        id[++cnt] = u; in[u] = cnt;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa) continue;
            dfs(v, u); id[++cnt] = u;
        } 
    }
    
    int st[maxn * 2][21], Log[maxn * 2];
    inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }
    void init_st(int n) { Log[0] = -1;
        for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
        for (int i = 1; i <= n; ++i) st[i][0] = id[i];
        for (int j = 1; j <= 20; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); 
    }
    inline int get(int l, int r) {
        l = in[l]; r = in[r]; if (l > r) swap(l, r);
        int k = Log[r - l + 1];
        return st_min(st[l][k], st[r - (1 << k) + 1][k]);
    }
}

int dep[maxn];
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; dfs(v, u); 
    } 
}

inline bool cmp(const int &u, const int &v) { return dep[u] > dep[v]; }

inline bool check(pair<int, int> path, int x) { 
    if (path.first <= 0) return false;
    auto [u, v] = path; int lca = LCA::get(u, v);
    if (LCA::get(lca, x) != lca) return false;
    if (LCA::get(u, x) != x && LCA::get(v, x) != x) return false;
    return true;
}

inline pair<int, int> merge(pair<int, int> u, pair<int, int> v) {
    auto [a, b] = u; auto [c, d] = v;
    if (!a || !c) return make_pair(a + c, b + d);
    if (a < 0 || c < 0) return make_pair(-1, -1); 
    int t[] = {LCA::get(a, c), LCA::get(a, d), LCA::get(b, c), LCA::get(b, d)}; sort(t, t + 4, cmp);
    if (t[0] != t[1] || dep[t[0]] == max(dep[LCA::get(a, b)], dep[LCA::get(c, d)]))
        return make_pair(t[0], t[1]);
    else return make_pair(-1, -1); 
}

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    pair<int, int> path; // (0, 0) 表示没有路径 (-1, -1) 表示路径为空
} T[maxm * 4];
inline void maintain(int i) {
    T[i].path = merge(T[lc].path, T[rc].path);
}

void update(int i, int l, int r, int k, pair<int, int> path) {
    if (l == r) return T[i].path = path, void();
    int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, path);
    else update(rc, m + 1, r, k, path);
    maintain(i);
}

pair<int, int> path;
int query(int i, int l, int r, int k) {
    if (!T[i].path.first || check(merge(path, T[i].path), k)) // 没有路径 || 路径交集不为空 && 点在路径上 
        return path = merge(path, T[i].path), 0;
    if (l == r) return l;
    int m = l + r >> 1, rs = query(rc, m + 1, r, k);
    if (rs) return rs;
    else return query(lc, l, m, k); 
}

struct Query {
    int opt, x, y, z, k; 
} Q[maxm]; int tp[maxm], id[maxm], cnt;

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } LCA::init(); LCA::dfs(1, 0); LCA::init_st(2 * n - 1); dep[1] = 1; dfs(1, 0);
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i].opt >> Q[i].x;
        if (!Q[i].opt) cin >> Q[i].y >> Q[i].z, id[++cnt] = i; 
    }
    for (int i = 1; i <= cnt; ++i) tp[i] = i;
    sort(tp + 1, tp + cnt + 1, [](const int &u, const int &v) { return Q[id[u]].z < Q[id[v]].z; });
    for (int i = 1; i <= cnt; ++i) Q[id[tp[i]]].k = i; Q[0].z = -1; 
    for (int i = 1; i <= m; ++i) {
        int opt = Q[i].opt, x = Q[i].x, y = Q[i].y, z = Q[i].z, k = Q[i].k;
        if (!opt) update(1, 1, cnt, k, make_pair(x, y));
        else if (opt == 1) update(1, 1, cnt, Q[x].k, make_pair(0, 0));
        else path = make_pair(0, 0), cout << Q[id[tp[query(1, 1, cnt, x)]]].z << "\n";
    }
    return 0;
}