結果

問題 No.650 行列木クエリ
ユーザー 0w10w1
提出日時 2018-04-14 17:05:56
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 3,541 bytes
コンパイル時間 2,531 ms
コンパイル使用メモリ 213,836 KB
実行使用メモリ 26,308 KB
最終ジャッジ日時 2023-09-09 05:16:07
合計ジャッジ時間 3,983 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,080 KB
testcase_01 AC 70 ms
8,740 KB
testcase_02 AC 123 ms
15,344 KB
testcase_03 AC 3 ms
7,080 KB
testcase_04 AC 71 ms
8,916 KB
testcase_05 AC 126 ms
15,328 KB
testcase_06 AC 3 ms
7,208 KB
testcase_07 AC 3 ms
7,132 KB
testcase_08 AC 56 ms
11,276 KB
testcase_09 AC 102 ms
26,308 KB
testcase_10 AC 3 ms
7,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
        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;
}
0