https://atcoder.jp/contests/past202010-open/tasks/past202010_m
前提知識
解説
https://atcoder.jp/contests/past202010-open/submissions/21473312
今回の問題はデータ構造で何とかなるので何とかした。
全然参考にならないかもしれない。
『データ構造』
以下のようなデータ構造を持っていれば解ける
そのまんまではあるが、上はHL分解で下は遅延評価セグメントツリーで実現できる。
int N, Q, A[101010], B[101010]; HLDecomposition hld; LazySegTree<int, 1 << 17> st; int ans[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> Q; hld.init(N); rep(i, 0, N - 1) { cin >> A[i] >> B[i]; A[i]--; B[i]--; hld.add(A[i], B[i]); } hld.build(0); rep(_, 0, Q) { int u, v, c; cin >> u >> v >> c; u--; v--; int lc = hld.lca(u, v); int tmp = st.get(hld.vid[lc], hld.vid[lc] + 1); hld.foreach(u, v, [&](int a, int b) { st.update(a, b + 1, c); }); st.update(hld.vid[lc], hld.vid[lc] + 1, tmp); } map<int, int> dic; rep(i, 0, N - 1) { int x = A[i]; int y = B[i]; if (hld.depth[x] > hld.depth[y]) swap(x, y); dic[y] = i; } rep(i, 1, N) { int c = st.get(hld.vid[i], hld.vid[i] + 1); ans[dic[i]] = c; } rep(i, 0, N - 1) printf("%d\n", ans[i]); }