Codeforces Round 767 (Div. 1) E. Groceries in Meteor Town (Kruskal重构树 + 线段树)

传送门

  出现最大路径权值就应该联想到克鲁斯卡尔重构树，我们对于克鲁斯卡尔重构树求一遍dfs序，维护所有白色点的最大最小dfn（包括出发点），求出最大最小dfn的最近公共祖先既是答案。注意需要特判一下除了本身以外没有白色点情况。

#include <bits/stdc++.h>

int n, m;
const int N = 6e5 + 10; 
typedef long long ll;
const int INF = 0x3f3f3f3f;
typedef std::array<int, 3> A;

std::vector<A> edge;

int a[N], val[N];

int h[N], ne[N], e[N], w[N], idx;

int fa[N][20], timedelta, id[N], rid[N], dep[N];

inline void add(int a, int b) {
	ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

int tot;

struct DSU {
    std::vector<int> f, sz;
    DSU(int n) : f(n + 1), sz(n + 1, 1) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) { return leader(x) == leader(y); }
    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        sz[x] += sz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return sz[leader(x)]; }
};

inline void Kruskal() {
	memset(h, -1, sizeof h);
	std::sort(edge.begin(), edge.end());
	DSU dsu(N);
	tot = n;
	for (int i = 0; i < n - 1; i ++) {
		auto &[v, a, b] = edge[i];
		a = dsu.leader(a), b = dsu.leader(b);
		val[++ tot] = v;
		dsu.f[tot] = dsu.f[a] = dsu.f[b] = tot;
		add(tot, a), add(tot, b);
	}
}

struct node {
	int l, r;
	int usedmx, usedmn;
	int mx, mn;
	int tag;
}tr[N << 2];

#define ls u << 1
#define rs u << 1 | 1

inline void pushup(int u) {
	tr[u].usedmx = std::max(tr[ls].usedmx, tr[rs].usedmx);
	tr[u].usedmn = std::min(tr[ls].usedmn, tr[rs].usedmn);
	tr[u].mx = std::max(tr[ls].mx, tr[rs].mx);
	tr[u].mn = std::min(tr[ls].mn, tr[rs].mn);
}

inline void build(int u, int l, int r) {
	tr[u].usedmx = 0, tr[u].usedmn = INF;
	if (l == r) {
		tr[u].mx = tr[u].mn = id[l];
		return ;
	}
	
	int mid = l + r >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	
	pushup(u);
}

inline void pushdown(int u) {
	if (tr[u].tag) {
		if (tr[u].tag == 1) {
			tr[ls].tag = tr[rs].tag = 1;
			tr[ls].usedmx = tr[ls].mx;
			tr[ls].usedmn = tr[ls].mn;
			tr[rs].usedmx = tr[rs].mx;
			tr[rs].usedmn = tr[rs].mn;
		} else {
			tr[ls].tag = tr[rs].tag = -1;
			tr[ls].usedmx = 0;
			tr[ls].usedmn = INF;
			tr[rs].usedmx = 0;
			tr[rs].usedmn = INF;
		}
		tr[u].tag = 0;
	}
}

inline void modify(int u, int L, int R, int l, int r, int x) {
	if (L >= l && R <= r) {
		if (x == 1) {
			tr[u].usedmx = tr[u].mx;
			tr[u].usedmn = tr[u].mn;
			tr[u].tag = 1;
		} else {
			tr[u].usedmx = 0;
			tr[u].usedmn = INF;
			tr[u].tag = -1;
		}
		return ;
	}
	
	pushdown(u);
	
	int mid = L + R >> 1;
	if (l <= mid)	modify(ls, L, mid, l, r, x);
	if (r > mid)	modify(rs, mid + 1, R, l, r, x);
	
	pushup(u);
}

inline void dfs(int u, int father, int depth) {
	fa[u][0] = father; 	id[u] = ++ timedelta, rid[timedelta] = u;
	dep[u] = depth;
	for (int i = 1; i <= 19; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];

	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		dfs(j, u, depth + 1);
	}
}

inline int LCA(int a, int b) {
	if (dep[a] < dep[b]) std::swap(a, b);
	for (int i = 19; ~i; i --) 
		if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
	
	if (a == b) return a;
	
	for (int i = 19; ~i; i --) 
		if (fa[a][i] != fa[b][i]) {
			a = fa[a][i];
			b = fa[b][i];
		}
	
	return fa[a][0];
}

#undef ls u << 1
#undef rs u << 1 | 1
inline void solve() {
	std::cin >> n >> m;
	
	for (int i = 0; i < n - 1; i ++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		edge.push_back({c, a, b});
	}

	Kruskal();
	
	dfs(tot, 0, 1);
	build(1, 1, n);
	
	while (m --) {
		int op;
		std::cin >> op;
		if (op <= 2) {
			int l, r;
			std::cin >> l >> r;
			if (op == 1) modify(1, 1, n, l, r, 1);
			else modify(1, 1, n, l, r, -1);
		} else {
			int x;
			std::cin >> x;
			int a = tr[1].usedmx, b = tr[1].usedmn;
			a = std::max(id[x], a), b = std::min(id[x], b);
			a = rid[a], b = rid[b];
			if (a == b) std::cout << -1 << '\n';
			else std::cout << val[LCA(a, b)] << '\n';
		}
	}
}

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	while (_ --) solve();
	
	return 0;
}