結果
問題 | No.650 行列木クエリ |
ユーザー |
|
提出日時 | 2018-04-14 16:20:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 3,575 bytes |
コンパイル時間 | 2,622 ms |
コンパイル使用メモリ | 210,908 KB |
最終ジャッジ日時 | 2025-01-05 10:12:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int M = 1e9 + 7;struct HLD {using Tree = vector<vector<int>>;vector<int> par, head, vid, len, inv;HLD(const Tree &g) : par(g.size()), head(g.size()), vid(g.size()), len(g.size()), inv(g.size()) {int k = 0;vector<int> size(g.size(), 1);function<void(int, int)> dfs_size = [&](int u, int p) {for (int v : g[u]) {if (v != p) {dfs_size(v, u);size[u] += size[v];}}};function<void(int, int, int)> dfs_dcmp = [&](int u, int p, int h) {par[u] = p;head[u] = h;vid[u] = k++;inv[vid[u]] = u;for (int v : g[u]) {if (v != p && size[u] < size[v] * 2) {dfs_dcmp(v, u, h);}}for (int v : g[u]) {if (v != p && size[u] >= size[v] * 2) {dfs_dcmp(v, u, v);}}};dfs_size(0, -1);dfs_dcmp(0, -1, 0);for (int i = 0; i < g.size(); ++i) {++len[head[i]];}}template<typename T>void foreach(int u, int v, T f) {while (true) {if (vid[u] > vid[v]) {if (head[u] == head[v]) {f(vid[v] + 1, vid[u], 0);break;} else {f(vid[head[u]], vid[u], 1);u = par[head[u]];}} else {if (head[u] == head[v]) {f(vid[u] + 1, vid[v], 0);break;} else {f(vid[head[v]], vid[v], 0);v = par[head[v]];}}}}};using Mat = array<array<int, 2>, 2>;constexpr Mat ONE = {array<int, 2>({1, 0}), array<int, 2>({0, 1})};Mat operator *(Mat a, Mat b) {Mat c = {array<int, 2>({0, 0}), array<int, 2>({0, 0})};for (int i = 0; i < 2; ++i) {for (int k = 0; k < 2; ++k) {for (int j = 0; j < 2; ++j) {(c[i][j] += 1LL * a[i][k] * b[k][j] % M) %= M;}}}return c;}template<typename T, int N>struct Seg {vector<T> dat;Seg() : dat(N * 2, ONE) {}void pull(int t) {dat[t] = dat[t << 1] * dat[t << 1 | 1];}void update(int t, int lb, int rb, int k, Mat m) {if (rb - lb == 1) {dat[t] = m;} else {int mb = lb + rb >> 1;if (k < mb) update(t << 1, lb, mb, k, m);else update(t << 1 | 1, mb, rb, k, m);pull(t);}}T query(int t, int lb, int rb, int ql, int qr) {if (qr <= lb || rb <= ql) return ONE;if (ql <= lb && rb <= qr) return dat[t];int mb = lb + rb >> 1;return query(t << 1, lb, mb, ql ,qr) * query(t << 1 | 1, mb, rb, ql, qr);}};signed main() {ios::sync_with_stdio(false);int N;cin >> N;vector<vector<int>> G(N);vector<int> U(N - 1), V(N - 1);for (int i = 0; i + 1 < N; ++i) {cin >> U[i] >> V[i];G[U[i]].emplace_back(V[i]);G[V[i]].emplace_back(U[i]);}HLD hld(G);Seg<Mat, 1 << 17> sgt;int Q;cin >> Q;while (Q--) {string OP;cin >> OP;if (OP == "g") {int u, v;cin >> u >> v;Mat res = ONE;hld.foreach(u, v, [&](int l, int r, int d) {if (d == 0) {res = sgt.query(1, 0, 1 << 17, l, r + 1) * res;}});cout << res[0][0] << ' ' << res[0][1] << ' ' << res[1][0] << ' ' << res[1][1] << endl;} else {int u;cin >> u;Mat m;for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {cin >> m[i][j];}}int x = hld.vid[U[u]] < hld.vid[V[u]] ? V[u] : U[u];sgt.update(1, 0, 1 << 17, hld.vid[x], m);}}return 0;}