「代码源挑战赛 R33F」最大边权

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

Description

Link：daimayuan 203

给出一棵包含 nn 个节点的树，边带权。

有 QQ 次询问，每次询问给出 kk 个区间 [l1,r1],⋯ ,[lk,rk][l_1, r_1], \cdots, [l_k, r_k]，定义点集 VV 表示至少被一个区间包含的点构成的集合。

考虑 VV 的所有无序点对 (u,v)(u, v)，将树上 u,vu, v 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。

数据范围：1≤n,Q≤2×1051 \leq n, Q\leq 2 \times 10^5，1≤∑k≤2×1051 \leq \sum k \leq 2 \times 10^5，1≤li≤ri≤n1 \leq l_i \leq r_i \leq n。

时空限制：22s / 512512MiB。

Solution

相当于是询问点集 VV 构成的虚树中，边权的最大值。

一个区间的情况

此时我们可以证明，区间 [l,r][l, r] 构成的虚树的边集，等价于所有 i,i+1i, i + 1（其中 l≤i<rl \leq i < r）之间简单路径边集的并。

证明也很简单：对于一条虚树中的边，将其中一侧子树的点标记为 A 类点，另一侧子树的点标记为 B 类点。则区间 [l,r][l, r] 中必定有相邻的两个点来自不同的类。

这样可以做到不漏但重复地统计，由于本题求的是最大值，所以不会有问题。

于是记 aia_i 表示 i,i+1i, i + 1 之间简单路径上边权的最大值。查询只需查询 al,⋯ ,ar−1a_l, \cdots, a_{r - 1} 的最大值即可。

多个区间的情况

现在考虑多个区间的情况，我们要考虑区间对区间的影响。如果我们将多个区间，顺次连接成一个区间，那么我们还是可以沿用刚刚查询相邻点贡献的最大值的思路。

仔细思考可以发现也并不需要顺次连接：对于两个区间的情况，只需要从两个区间中各选一个点出来，查询即可。

对于 kk 个区间的情况也是同理，先在第一个区间中任选一个点 pp，再在第 i(2≤i≤k)i(2 \leq i \leq k) 个区间中任选一个点出来和 pp 查询即可。

显然这样也可以覆盖到所有虚树上的边。

时间复杂度 O((n+∑k)log⁡n)\mathcal{O}((n + \sum k) \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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 200100;

int n, Q;

struct Graph {
    std::vector< std::vector< std::pair<int, int> > > table;

    void init(int _n) {
        table.assign(_n + 1, {});
    }

    void add_edge(int u, int v, int w) {
        table[u].push_back({v, w});
    }
} G;

int dep[N];
int anc[18][N];
int val[18][N];

void dfs_init(int u, int fu) {
    dep[u] = dep[fu] + 1;

    anc[0][u] = fu;
    for (int i = 1; i <= 17; i ++) {
        anc[i][u] = anc[i - 1][anc[i - 1][u]];
        val[i][u] = std::max(val[i - 1][u], val[i - 1][anc[i - 1][u]]);
    }

    for (auto [v, w] : G.table[u]) {
        if (v == fu) {
            continue;
        }
        val[0][v] = w;
        dfs_init(v, u);
    }
}

int calc(int x, int y) {
    int ans = 0;
    if (dep[x] > dep[y]) std::swap(x, y);
    for (int i = 17; i >= 0; i --) {
        if (dep[x] <= dep[y] - (1 << i)) {
            chmax(ans, val[i][y]);
            y = anc[i][y];
        }
    }
    if (x == y) return ans;
    for (int i = 17; i >= 0; i --) {
        if (anc[i][x] ^ anc[i][y]) {
            chmax(ans, val[i][x]), chmax(ans, val[i][y]);
            x = anc[i][x], y = anc[i][y];
        }
    }
    chmax(ans, val[0][x]), chmax(ans, val[0][y]);
    return ans;
}

int a[N];

namespace ST {
    int logn;
    std::vector< std::vector<int> > f;

    void init() {
        logn = std::__lg(n);
        f.assign(logn + 1, std::vector<int>(n + 1, 0));
        
        for (int i = 1; i <= n; i ++) {
            f[0][i] = a[i];
        }
        for (int j = 1; j <= logn; j ++) {
            for (int i = 1; i <= n - (1 << j) + 1; i ++) {
                f[j][i] = std::max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    int ask(int l, int r) {
        int k = std::__lg(r - l + 1);
        return std::max(f[k][l], f[k][r - (1 << k) + 1]);
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> Q;
    
    G.init(n);
    for (int i = 1; i < n; i ++) {
        int x, y, z;
        std::cin >> x >> y >> z;

        G.add_edge(x, y, z), G.add_edge(y, x, z);
    }

    dfs_init(1, 0);

    for (int i = 1; i < n; i ++) {
        a[i] = calc(i, i + 1);
    }

    ST::init();

    while (Q --) {
        int k;
        std::cin >> k;

        int ans = 0;
        int p = -1;
        for (int i = 1; i <= k; i ++) {
            int l, r;
            std::cin >> l >> r;

            if (l < r) {
                chmax(ans, ST::ask(l, r - 1));
            }

            if (p == -1) {
                p = l;
            } else {
                chmax(ans, calc(p, l));
            }
        }

        std::cout << ans << '\n';
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/