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()); } } }