結果

問題 No.650 行列木クエリ
ユーザー 0w10w1
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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