筆塗り [第四回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202010-open/tasks/past202010_m

前提知識

• HL分解
• 遅延評価セグメントツリー

解説

https://atcoder.jp/contests/past202010-open/submissions/21473312

今回の問題はデータ構造で何とかなるので何とかした。
全然参考にならないかもしれない。

『データ構造』

以下のようなデータ構造を持っていれば解ける

• 木上において頂点Aから頂点Bへの最短経路上の頂点に対して高速に少ないグループ数の区間を提供できる
• ある区間に対してある数を高速に代入できる

そのまんまではあるが、上は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]);
}