P10238 [yLCPC2024] F. PANDORA PARADOXXX

P10238 [yLCPC2024] F. PANDORA PARADOXXX

并查集维护连通性+结论+数据结构维护距离

题目的操作是删边通常复杂，并且不强制在线，所以离线倒过来加边。

题目要求的就是当前所有连通块的直径的最大值，考虑加边后两个连通块合并后直径的变化。有结论：合并后的连通块的直径两端点一定是合并前两个连通块的直径端点其二。

证明：设两个连通块的端点分别为 \((a,b)\)、\((c,d)\)。假如合并后直径没有跨越两个连通块，那么直径显然还是 \((a,b)\) 或 \((c,d)\)；否则设连接两个连通块的边为 \((x,y)\)，根据直径的性质，到 \(x\) 最远的点为 \(a\) 或 \(b\)，到 \(y\) 最远的点为 \(c\) 或 \(d\)。那么直径的端点还是其二。

于是考虑维护连通块中的直径端点。初始每个点为一个连通块，每次加边求出新的直径。这些可以用并查集维护。关于每条路径的距离如何求，由于合并完的连通块一定是原先树的一部分，所以我们在原先的树上预处理出 \(dis\) 和 \(lca\) 等信息即可。

复杂度 \(O(n\log n)\)，带一些小常数。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
int n, q, cnt;
i64 ret;
int h[N];
std::vector<pii> E, G;
i64 dep[N], sz[N], top[N], fa[N], son[N], dis[N], ans[N];
struct node {
	int to, nxt; i64 w;
} e[N << 1];
void add(int u, int v, i64 w) {
	e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].w = w, h[u] = cnt;
}
void dfs1(int u, int f) {
	dep[u] = dep[f] + 1;
	fa[u] = f;
	sz[u] = 1;
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].w;
		if(v == f) continue;
		dis[v] = dis[u] + w; 
		dfs1(v, u);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]]) son[u] = v;	
	}
}
void dfs2(int u, int topf) {
	top[u] = topf;
	if(!son[u]) return;
	dfs2(son[u], topf);
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
int lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) std::swap(u, v);
	return u;
}
i64 D(int u, int v) {
	int rt = lca(u, v);
	return dis[u] + dis[v] - 2 * dis[rt];
}

struct Union {
	int fa[N], l[N], r[N];
	int find(int x) {
		if(x != fa[x]) fa[x] = find(fa[x]);
		return fa[x];
	}
} U;
void mg(int u, int v) {
	int fu = U.find(u), fv = U.find(v);
	pii ve[6] = {{U.l[fu], U.r[fu]}, {U.l[fu], U.l[fv]}, {U.l[fu], U.r[fv]},
				 {U.r[fu], U.l[fv]}, {U.r[fu], U.r[fv]}, {U.l[fv], U.r[fv]}};
	i64 res = 0, ru, rv;
	for(int i = 0; i < 6; i++) {
 		if(res < D(ve[i].fi, ve[i].se)) {
 			res = D(ve[i].fi, ve[i].se), ru = ve[i].fi, rv = ve[i].se; 
 		}
	}
	ret = std::max(ret, res);
	U.fa[fv] = fu;
	U.l[fu] = ru, U.r[fu] = rv;
}
void Solve() {
	std::cin >> n >> q;

	E.pb({0, 0}), G.pb({0, 0});
	for(int i = 1; i < n; i++) {
		int u, v; i64 w;
		std::cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
		E.pb({u, v});
	}
	dfs1(1, 0), dfs2(1, 1);
	for(int i = 1; i <= q; i++) {
		int x;
		std::cin >> x;
		G.pb(E[x]), E[x] = {0, 0};
	}
	for(auto x : E) {
		if(x.fi) G.pb({x.fi, x.se});
	}
	std::reverse(G.begin() + 1, G.end());
	for(int i = 1; i <= n; i++) U.fa[i] = U.l[i] = U.r[i] = i;
	for(int i = 1; i < n; i++) {
		ans[i] = ret;
		mg(G[i].fi, G[i].se);
	}

	for(int i = n - 1; i >= n - q; i--) std::cout << ans[i] << "\n";
	E.clear(), G.clear();
	for(int i = 1; i <= n; i++) U.fa[i] = U.l[i] = U.r[i] = h[i] = dep[i] = dis[i] = son[i] = fa[i] = sz[i] = top[i] = ans[i] = 0; 
	cnt = ret = 0;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;

	while(T--) Solve();

	return 0;
}