「代码源挑战赛 R33F」最大边权
给出一棵包含 n 个节点的树,边带权。
有 Q 次询问,每次询问给出 k 个区间 [l_1, r_1], \dots, [l_k, r_k],定义点集 V 表示至少被一个区间包含的点构成的集合。
考虑 V 的所有无序点对 (u, v),将树上 u, v 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。
数据范围:1 \leq n, Q\leq 2 \times 10^5,1 \leq \sum k \leq 2 \times 10^5,1 \leq l_i \leq r_i \leq n。
时空限制:2s / 512MiB。
Solution
相当于是询问点集 V 构成的虚树中,边权的最大值。
一个区间的情况
此时我们可以证明,区间 [l, r] 构成的虚树的边集,等价于所有 i, i + 1(其中 l \leq i < r)之间简单路径边集的并。
证明也很简单:对于一条虚树中的边,将其中一侧子树的点标记为 A 类点,另一侧子树的点标记为 B 类点。则区间 [l, r] 中必定有相邻的两个点来自不同的类。
这样可以做到不漏但重复地统计,由于本题求的是最大值,所以不会有问题。
于是记 a_i 表示 i, i + 1 之间简单路径上边权的最大值。查询只需查询 a_l, \dots, a_{r - 1} 的最大值即可。
多个区间的情况
现在考虑多个区间的情况,我们要考虑区间对区间的影响。如果我们将多个区间,顺次连接成一个区间,那么我们还是可以沿用刚刚查询相邻点贡献的最大值的思路。
仔细思考可以发现也并不需要顺次连接:对于两个区间的情况,只需要从两个区间中各选一个点出来,查询即可。
对于 k 个区间的情况也是同理,先在第一个区间中任选一个点 p,再在第 i (2 \leq i \leq k) 个区间中任选一个点出来和 p 查询即可。
显然这样也可以覆盖到所有虚树上的边。
时间复杂度 \mathcal{O}((n + \sum k) \log n)。
#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;
}
/**
* 心中无女人
* 比赛自然神
* 模板第一页
* 忘掉心上人
**/