Disruption

Explicación

Enraizamos el árbol de forma arbitraria. Cada camino original desprende un subárbol del resto del árbol. Para que una arista de reemplazo sustituya este camino, uno de sus extremos debe estar en el subárbol desprendido y el otro extremo debe estar fuera del subárbol. Para resolver el problema, necesitamos hallar la arista de longitud mínima entre todas estas aristas posibles.

Para calcularlo, recorremos el árbol con un DFS, calculando el conjunto de aristas posibles para el subárbol de cada nodo. Para calcular el conjunto del nodo actual, fusionamos los conjuntos de sus hijos, insertamos en el conjunto todas las aristas de reemplazo de las que este nodo es un extremo, y eliminamos todas las aristas donde este nodo es el ancestro común más bajo de los extremos (porque ambos extremos de estas aristas están en el subárbol del nodo actual). Esto corre en $\mathcal{O}(NM \log M)$ .

Podemos optimizarlo usando fusión small-to-large al fusionar los conjuntos de los nodos hijos. Cada inserción mueve un elemento a un conjunto al menos el doble de grande que antes, así que cada elemento se inserta a lo sumo $O(\log M)$ veces, lo que significa que la complejidad temporal del DFS es $O(N + M \log^2 M)$ .

Implementación

Complejidad temporal: $\mathcal{O}(N \log N + M \log^2 M)$ , aunque la complejidad temporal de soluciones similares puede variar según cómo se implemente el LCA.

C++


#include <bits/stdc++.h>
using namespace std;
 
int bit_width(int x) { return __lg(x) + 1; }
 
// BeginCodeSnip{LCA}
struct LCA {
	using Tree = const vector<vector<int>>;
	int n, k, root;
	vector<int> first, depth, parent, tour;
	vector<vector<int>> st;
 
	void dfs(Tree &adj, int node, int par) {
		parent[node] = par;
		if (par != -1) depth[node] = depth[par] + 1;
		first[node] = tour.size();
		tour.push_back(node);
		for (int i : adj[node]) {
			if (i != par) {
				dfs(adj, i, node);
				tour.push_back(node);
			}
		}
	}
 
	int min_depth(int x, int y) { return depth[x] < depth[y] ? x : y; }
 
	LCA(Tree &adj, int root = 0)
	    : n(adj.size()), k(bit_width(2 * n - 1)), root(root), first(n), depth(n),
	      parent(n), st(k) {
		tour.reserve(2 * n - 1);
		dfs(adj, root, -1);
 
		st[0] = tour;
		int pow = 2;
		for (int i = 1; i < k; i++) {
			st[i].resize(2 * n - pow);
			for (int j = 0; j < 2 * n - pow; j++) {
				st[i][j] = min_depth(st[i - 1][j], st[i - 1][j + pow / 2]);
			}
			pow <<= 1;
		}
	}
 
	int lca(int a, int b) {
		int l = first[a], r = first[b];
		if (l > r) swap(l, r);
		int i = bit_width(r - l + 1) - 1;
		return min_depth(st[i][l], st[i][r - (1 << i) + 1]);
	}
 
	bool is_ancestor(int a, int b) { return lca(a, b) == a; }
 
	int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
};
// EndCodeSnip
 
int n, m;
vector<vector<int>> adj;
vector<int> ans;
vector<vector<int>> add, rem;
 
multiset<int> dfs(int i, int p) {
	// Merge sets of children
	multiset<int> s;
	for (int j : adj[i])
		if (j != p) {
			auto ss = dfs(j, i);
			if (ss.size() > s.size()) swap(s, ss);
			s.insert(ss.begin(), ss.end());
		}
	// Insert edges where i is an endpoint
	for (int j : add[i]) s.insert(j);
	// Remove edges where i is the LCA of the endpoints
	// They are removed twice because edges are added once for each point
	for (int j : rem[i]) s.erase(s.find(j)), s.erase(s.find(j));
	// Calculate answer for this edge
	if (s.size()) ans[i] = *s.begin();
	return s;
}
 
void solve() {
	cin >> n >> m;
	adj.resize(n);
	vector<pair<int, int>> edges;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		edges.push_back({a, b});
	}
 
	// Precompute LCA
	LCA lca(adj);
 
	// Each edge will be inserted at both endpoints and removed at their LCA
	add.resize(n);
	rem.resize(n);
	while (m--) {
		int p, q, r;
		cin >> p >> q >> r;
		int l = lca.lca(--p, --q);
		add[p].push_back(r);
		add[q].push_back(r);
		rem[l].push_back(r);
	}
 
	// dfs
	ans.assign(n, -1);
	dfs(0, -1);
 
	// output answer
	for (auto &[a, b] : edges) {
		// a is the higher node
		if (lca.depth[a] < lca.depth[b]) swap(a, b);
		cout << ans[a] << '\n';
	}
}
 
signed main() {
	freopen("disrupt.in", "r", stdin);
	freopen("disrupt.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);
	solve();
}