結果
問題 | No.650 行列木クエリ |
ユーザー |
|
提出日時 | 2018-02-09 23:16:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 4,088 bytes |
コンパイル時間 | 1,208 ms |
コンパイル使用メモリ | 87,828 KB |
実行使用メモリ | 30,688 KB |
最終ジャッジ日時 | 2024-10-09 09:01:10 |
合計ジャッジ時間 | 2,856 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#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;Seg seg1;int q = input();while (q--) {char c;cin >> c;if (c == 'g') {int u = input();int v = input();M resL = one;M resR = one;hld.foreach(u, v, [&](int l, int r, int d) {if (d == 0) {resR = seg0.query(l, r) * resR;} else {resL = resL * seg1.query(hld.rev(r), hld.rev(l));}});resL = resL * resR;printf("%d %d %d %d\n", resL[0][0].n, resL[0][1].n, resL[1][0].n, resL[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);seg1.update(hld.rev(hld.vid[x]), m);}}}