前置知识
- 线段树
- \(\text{Kruskal}\) 重构树
- 点集 \(\text{LCA}\)
思路
看到询问为 \(x\) 到所有白色节点的路径上最大可能边权，可以利用 \(\text{Kruskal}\) 重构树转化为 \(x\) 与所有白色点的 \(\text{lca}\) 的权值。
问题在于如何快速求出一个点集的 \(\text{lca}\)，参考 CF1062E 中的套路，维护点集中 \(\text{dfs}\) 序最大以及最小的两个点，求这两个点的 \(\text{lca}\) 即为这个点集的 \(\text{lca}\)。
具体实现先建出 \(\text{Kruskal}\) 重构树，然后建线段树维护区间 \(\text{dfn}\) 最大最小值。对于修改操作，如果为操作 \(1\) 则更新该区间 \(\text{dfn}\) 最大值最小值，否则清空该区间。对于询问操作，查询全局 \(\text{dfn}\) 最大最小值，与 \(x\) 的 \(\text{dfn}\) 合并，求 \(\text{lca}\) 权值。
时间复杂度 \(O(n \log n + q \log n)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define l(x) x<<1
#define r(x) x<<1|1
const int SIZE = 600005;
const int mod = 998244353;
int n, T, totv;
int head[SIZE], ver[SIZE*2], nxt[SIZE*2], tot;
int dfn[SIZE], id[SIZE], sum[SIZE], iid;
int a[SIZE], fa[SIZE], d[SIZE], f[SIZE][30];
inline int rd(){
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return f*x;
}
struct E{
int x, y, val;
}e[SIZE];
int get(int x){
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
bool cmp(E x, E y){
return x.val < y.val;
}
void add(int x, int y){
ver[++tot] = y, nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int x, int ffa){
dfn[x] = ++iid; id[dfn[x]] = x; d[x] = d[ffa] + 1; f[x][0] = ffa;
for(int i = 1; i <= 25; i++) f[x][i] = f[f[x][i-1]][i-1];
for(int i = head[x]; i; i = nxt[i]){
int y = ver[i];
if(y == ffa) continue;
dfs(y, x);
}
}
int LCA(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = 25; i >= 0; i--){
if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
}
for(int i = 25; i >= 0; i--){
if(f[x][i] != f[y][i]){
x = f[x][i], y = f[y][i];
}
}
return f[x][0];
}
struct Tree{
int l, r;
int Maxx, Minx;
int Max, Min;
int tag;
}t[SIZE<<2];
void pushup(int p){
t[p].Max = max(t[l(p)].Max, t[r(p)].Max);
t[p].Min = min(t[l(p)].Min, t[r(p)].Min);
t[p].Maxx = max(t[l(p)].Maxx, t[r(p)].Maxx);
t[p].Minx = min(t[l(p)].Minx, t[r(p)].Minx);
}
void pushdown(int p){
if(t[p].tag != -1){
if(t[p].tag){
t[l(p)].Max = t[l(p)].Maxx;
t[l(p)].Min = t[l(p)].Minx;
t[r(p)].Max = t[r(p)].Maxx;
t[r(p)].Min = t[r(p)].Minx;
}
else{
t[l(p)].Max = 0, t[l(p)].Min = (1<<30);
t[r(p)].Max = 0, t[r(p)].Min = (1<<30);
}
t[l(p)].tag = t[p].tag, t[r(p)].tag = t[p].tag;
t[p].tag = -1;
}
}
void Build(int p, int l, int r){
t[p].l = l, t[p].r = r; t[p].tag = -1;
if(l == r){
t[p].Max = 0, t[p].Min = (1<<30);
t[p].Maxx = t[p].Minx = dfn[l];
return;
}
int mid = (l + r) >> 1;
Build(l(p), l, mid);
Build(r(p), mid+1, r);
pushup(p);
}
void change(int p, int l, int r, int kk){
if(l <= t[p].l && r >= t[p].r){
if(kk){
t[p].Max = t[p].Maxx;
t[p].Min = t[p].Minx;
}
else{
t[p].Max = 0, t[p].Min = (1<<30);
}
t[p].tag = kk;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if(l <= mid) change(l(p), l, r, kk);
if(r > mid) change(r(p), l, r, kk);
pushup(p);
}
int main(){
n = rd(), T = rd();
for(int i = 1; i < n; i++){
e[i].x = rd(), e[i].y = rd(), e[i].val = rd(); fa[i] = i;
}
for(int i = n; i <= 2*n; i++) fa[i] = i;
sort(e+1, e+n, cmp); totv = n;
for(int i = 1; i < n; i++){
int x = e[i].x, y = e[i].y, val = e[i].val;
int xx = get(x), yy = get(y);
if(xx == yy) continue;
totv++;
add(xx, totv); add(totv, xx);
add(yy, totv); add(totv, yy);
a[totv] = val;
fa[xx] = totv;
fa[yy] = totv;
}
dfs(totv, 0);
Build(1, 1, n);
while(T--){
int op = rd();
if(op == 1){
int l = rd(), r = rd();
change(1, l, r, 1);
}
else if(op == 2){
int l = rd(), r = rd();
change(1, l, r, 0);
}
else{
int x = rd();
int Min = t[1].Min, Max = t[1].Max;
Min = min(Min, dfn[x]);
Max = max(Max, dfn[x]);
if(Min == (1<<30)){
printf("-1\n");
continue;
}
int x1 = id[Max], x2 = id[Min];
int cc = LCA(x1, x2);
if(a[cc] == 0) printf("-1\n");
else printf("%d\n", a[cc]);
}
}
return 0;
}