はまやんはまやんはまやん

hamayanhamayan's blog

行列木クエリ [yukicoder No.650]

https://yukicoder.me/problems/no/650

解法

https://yukicoder.me/submissions/235253

木上でのクエリを処理するので、HL分解+セグメントツリーのいつものペアかなと考えるといつものペアである。
辺でのクエリであるが、下の頂点に対応させれば、頂点でのクエリとして扱える。
「f[i] := 辺iのうち根から遠い方の頂点」として辺の更新もこれを使おう。
 
セグメントツリーには2*2の行列を乗せておく。
更新は行列の積を用いて、更新する時は左と右の関係を壊さないように更新する。
自分の実装だけかもしれないが、HL分解する場合に左右の関係が壊れてしまう恐れがある。
深さを使ってどちらで掛けるかを調整すると上手くいく。
この辺はHL分解の実装によって色々変化する必要がある。
適当にやったら通った感がある。チャレンジされるかも。

int N, Q, A[101010], B[101010];
int f[101010];
SegTree<func, 1 << 17> st;
HLDecomposition hld;
func ans; int pre;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    hld.init(N);

    rep(i, 0, N - 1) {
        cin >> A[i] >> B[i];
        hld.add(A[i], B[i]);
    }
    hld.build();

    rep(i, 0, N - 1) {
        if (hld.depth[A[i]] < hld.depth[B[i]]) f[i] = B[i];
        else f[i] = A[i];
    }

    cin >> Q;
    rep(q, 0, Q) {
        string t; cin >> t;
        if (t == "x") {
            int i, a, b, c, d;
            cin >> i >> a >> b >> c >> d;
            i = f[i];
            st.update(hld.vid[i], func(a, b, c, d));
        } else {
            int i, j; cin >> i >> j;

            i = hld.go(i, j, 1);

            ans = func();
            pre = -1;
            hld.foreach(j, i, [](int u, int v) {
                int uu = hld.inv[u];
                if (pre < hld.depth[uu]) ans = ans * st.get(u, v + 1);
                else ans = st.get(u, v + 1) * ans;
                pre = hld.depth[uu];
            });

            printf("%d %d %d %d\n", ans.x00.get(), ans.x01.get(), ans.x10.get(), ans.x11.get());
        }
    }
}