結果

問題 No.650 行列木クエリ
ユーザー pekempeypekempey
提出日時 2018-02-09 23:31:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 3,958 bytes
コンパイル時間 1,196 ms
コンパイル使用メモリ 86,860 KB
実行使用メモリ 26,772 KB
最終ジャッジ日時 2024-10-09 09:03:21
合計ジャッジ時間 2,402 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,552 KB
testcase_01 AC 49 ms
9,216 KB
testcase_02 AC 107 ms
15,948 KB
testcase_03 AC 5 ms
7,552 KB
testcase_04 AC 51 ms
9,344 KB
testcase_05 AC 109 ms
15,808 KB
testcase_06 AC 5 ms
7,424 KB
testcase_07 AC 5 ms
7,424 KB
testcase_08 AC 53 ms
11,520 KB
testcase_09 AC 98 ms
26,772 KB
testcase_10 AC 5 ms
7,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <functional>

using namespace std;

const int mod = 1e9 + 7;

struct Modint {
  int n;
  Modint(int n = 0) : n(n) {}
};

Modint operator+(Modint a, Modint b) { return Modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
Modint operator-(Modint a, Modint b) { return Modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
Modint operator*(Modint a, Modint b) { return Modint(1LL * a.n * b.n % mod); }
Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
Modint &operator*=(Modint &a, Modint b) { return a = a * b; }

using V = array<Modint, 2>;
using M = array<V, 2>;

M one = { V { 1, 0 }, V { 0, 1 } };

M operator *(M a, M b) {
  M res = {};
  for (int i = 0; i < 2; i++) {
    for (int k = 0; k < 2; k++) {
      for (int j = 0; j < 2; j++) {
        res[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return res;
}

struct HLD {
  using Tree = std::vector<std::vector<int>>;
  std::vector<int> parent, head, vid, len, inv;

  HLD(const Tree &g) : parent(g.size()), head(g.size()), vid(g.size()), len(g.size()), inv(g.size()) {
    int k = 0;
    std::vector<int> size(g.size(), 1);
    std::function<void(int, int)> dfs = [&](int u, int p) {
      for (int v : g[u]) if (v != p) dfs(v, u), size[u] += size[v];
    };
    std::function<void(int, int, int)> dfs2 = [&](int u, int p, int h) {
      parent[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) dfs2(v, u, h);
      for (int v : g[u]) if (v != p && size[u] >= size[v] * 2) dfs2(v, u, v);
    };
    dfs(0, -1);
    dfs2(0, -1, 0);
    for (int i = 0; i < g.size(); i++) {
      len[head[i]]++;
    }
  }

  int rev(int u) {
    int h = head[inv[u]];
    int offset = u - vid[h];
    return vid[h] + len[h] - 1 - offset;
  }

  template<class 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 = parent[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 = parent[head[v]];
        }
      }
    }
  };
};

const int N = 1 << 17;

struct Seg {
  vector<M> dat;

  Seg() : dat(N * 2, one) {}

  void update(int k, M m) {
    dat[k + N] = m;
    for (int i = k + N >> 1; i > 0; i >>= 1) {
      dat[i] = dat[i * 2] * dat[i * 2 + 1];
    }
  }

  M query(int l, int r) {
    M resL = one;
    M resR = one;
    r++;
    l += N;
    r += N;
    while (l < r) {
      if (l & 1) resL = resL * dat[l++];
      if (r & 1) resR = dat[--r] * resR;
      l >>= 1;
      r >>= 1;
    }
    return resL * resR;
  }
};

int input() {
  int n;
  scanf("%d", &n);
  return n;
}

int main() {
  int n = input();
  
  vector<vector<int>> g(n);
  vector<int> us(n - 1);
  vector<int> vs(n - 1);
  for (int i = 0; i < n - 1; i++) {
    int u = input();
    int v = input();
    us[i] = u;
    vs[i] = v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  HLD hld(g);

  // 先祖間クエリしか来ないのね…
  Seg seg0;

  int q = input();

  while (q--) {
    char c;
    cin >> c;

    if (c == 'g') {
      int u = input();
      int v = input();

      M resR = one;

      hld.foreach(u, v, [&](int l, int r, int d) {
        if (d == 0) {
          resR = seg0.query(l, r) * resR;
        }
      });
      printf("%d %d %d %d\n", resR[0][0].n, resR[0][1].n, resR[1][0].n, resR[1][1].n);
    } else {
      int u = input();
      M m;
      for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
          m[i][j] = input();
        }
      }
      int x = hld.vid[us[u]] < hld.vid[vs[u]] ? vs[u] : us[u];
      seg0.update(hld.vid[x], m);
    }
  }
}
0