結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 はむこ
|
| 提出日時 | 2016-09-19 23:19:09 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,557 bytes |
| コンパイル時間 | 2,267 ms |
| コンパイル使用メモリ | 194,580 KB |
| 実行使用メモリ | 35,144 KB |
| 最終ジャッジ日時 | 2024-07-18 01:24:03 |
| 合計ジャッジ時間 | 6,698 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
13,884 KB |
| testcase_01 | AC | 87 ms
9,600 KB |
| testcase_02 | AC | 205 ms
35,028 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 89 ms
9,600 KB |
| testcase_05 | AC | 199 ms
35,144 KB |
| testcase_06 | AC | 2 ms
6,944 KB |
| testcase_07 | AC | 2 ms
6,944 KB |
| testcase_08 | TLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define Min(x) *min_element(all(x))
#define Max(x) *max_element(all(x))
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) { o << "(" << v.first << ", " << v.second << ")"; return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { if (!v.empty()) { o << '['; copy(v.begin(), v.end(), ostream_iterator<T>(o, ", ")); o << "\b\b]"; } return o; }
using ll = long long; using ld = long double; using vll = vector<ll>; using vi = vector<int>;
typedef pair<ld, ld> P;
static const double EPS = 1e-14;
static const long long INF = 1e18;
#define MAX_N 100005
class Mod {
public:
int num;
int mod;
Mod() : Mod(0) {}
Mod(long long int n) : Mod(n, 1000000007) {}
Mod(long long int n, int m) { mod = m; num = (n % mod + mod) % mod;}
Mod(const string &s){ long long int tmp = 0; for(auto &c:s) tmp = (c-'0'+tmp*10) % mod; num = tmp; }
Mod(int n) : Mod(static_cast<long long int>(n)) {}
operator int() { return num; }
void setmod(const int mod) { this->mod = mod; }
};
istream &operator>>(istream &is, Mod &x) { long long int n; is >> n; x = n; return is; }
ostream &operator<<(ostream &o, const Mod &x) { o << x.num; return o; }
Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % a.mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((a.mod + a.num - b.num) % a.mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % a.mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod factorial(const long long n) {
if (n < 0) return 0;
Mod ret = 1;
for (int i = 1; i <= n; i++) {
ret *= i;
}
return ret;
}
Mod operator^(const Mod a, const long long n) {
if (n == 0) return Mod(1);
Mod res = (a * a) ^ (n / 2);
if (n % 2) res = res * a;
return res;
}
Mod modpowsum(const Mod a, const long long b) {
if (b == 0) return 0;
if (b % 2 == 1) return modpowsum(a, b - 1) * a + Mod(1);
Mod result = modpowsum(a, b / 2);
return result * (a ^ (b / 2)) + result;
}
/*************************************/
// GF(p)の行列演算
/*************************************/
using number = Mod;
using arr = vector<number>;
using matrix = vector<vector<Mod>>;
ostream &operator<<(ostream &o, const arr &v) { rep(i, v.size()) cout << v[i] << " "; cout << endl; return o; }
ostream &operator<<(ostream &o, const matrix &v) { rep(i, v.size()) cout << v[i]; return o; }
matrix zero(int n) { matrix A(n, arr(n, 0)); return A; } // O(n^2)
matrix identity(int n) { matrix A(n, arr(n, 0)); rep(i, n) A[i][i] = 1; return A; } // O(n^2)
// O(n^3)
matrix mul(const matrix &A, const matrix &B) {
matrix C(A.size(), arr(B[0].size(), 0));
rep(i, C.size())
rep(j, C[i].size())
rep(k, A[i].size())
C[i][j] += A[i][k] * B[k][j];
return C;
}
// O(n^2)
matrix plu(const matrix &A, const matrix &B) {
matrix C(A.size(), arr(B[0].size(), 0));
rep(i, C.size())
rep(j, C[i].size())
C[i][j] += A[i][j] + B[i][j];
return C;
}
// 静的木
//
// 構築O(n): オイラーツアー, 木の高さ, 祖先ダブリング
//
// LCA O(log n)
// 頂点間最小辺数 O(log n)
// 頂点から根までのパスの二分探索 O(log n)
struct edge_t { int from, to; ll weight; };
using verticle_t = ll;
class Tree {
public:
int MAXLOGV;
vector<vector<edge_t>> m_edges; // m_edges[i][j]が存在: i->jの辺が存在
int vn; // 頂点の数, vn<2^MAXLOGV
int root; // 根ノードの番号
vector<verticle_t> m_verticles;
vector<vector<verticle_t>> m_verticles_doubling; // m_verticles_doubling[i][j]: jのi^2番目の親までのm_vertivlesの結合演算opによる積分
vector<vector<int>> parent; // parent[i][j]: jのi^2番目の親。j=0で直近の親。
vector<int> depth; // depth[i]: 頂点iの根からの深さ, 根が0
/*********/
// 構築
/*********/
Tree(int vn, int root) : vn(vn), root(root) {
// TODO このへんの確保を最低限に
MAXLOGV = ceil(log(vn) / log(2)) + 2; // +2は念の為
m_edges.resize(vn);
m_verticles.resize(vn);
parent.resize(MAXLOGV); rep(i, MAXLOGV) parent[i].resize(vn);
depth.resize(vn);
}
// 辺の構築
void unite(edge_t e) {
m_edges[e.from].push_back({e.from, e.to, e.weight});
m_edges[e.to].push_back({e.to, e.from, e.weight});
}
void unite(int u, int v) {
unite({u, v, 1});
}
// 頂点の構築
void setVerticle(int i, verticle_t v) {
m_verticles_doubling[0][i] = m_verticles[i] = v;
}
// rootからの深さと親を確認。
// uniteし終わったらまずこれを呼ぶこと。
void init() {
dfs(root, -1, 0);
for (int k = 0; k+1 < MAXLOGV; k++) // 2^k代祖先を計算
for (int v = 0; v < vn; v++)
if (parent[k][v] < 0)
parent[k+1][v] = -1; // 2^k代親が根を超えてるなら、2^(k+1)代親も根を超える
else
parent[k+1][v] = parent[k][parent[k][v]]; // 2^(k+1)代の親は、2^k代親の2^k代親
// 親のダブリング
rep(k, MAXLOGV - 1) // 2^k代祖先を計算
for (int v = 0; v < vn; v++)
if (parent[k][v] < 0)
parent[k+1][v] = -1; // 2^k代親が根を超えてるなら、2^(k+1)代親も根を超える
else
parent[k+1][v] = parent[k][parent[k][v]]; // 2^(k+1)代の親は、2^k代親の2^k代親
}
// 1つ親と深さとオイラーツアーを構築
// TODO 機能毎に分ける
void dfs(int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for (edge_t next : m_edges[v])
if (next.to != p)
dfs(next.to, v, d+1);
}
// 木の直径を求める
// 辺が重み付きでもOK!
//
// O(V)
ll diameter(void) {
using Result = pair<ll, int>;
function<Result(int, int)> visit = [&](int p, int v){
Result r(0, v);
for (auto e : m_edges[v]) if (e.to != p) {
Result t = visit(v, e.to);
t.first += e.weight;
if (r.first < t.first) r = t;
}
return r;
};
Result r = visit(-1, 0);
Result t = visit(-1, r.second);
// このあと、r, tからの距離を使って木の中心を求めることができる。O(V)
// t.firstが偶数なら、rからt.first/2かつtからt.first/2の距離
// t.firstが偶数なら、rからt.first/2+1or+0かつtからt.first/2+1or+0の距離の二点
return t.first; // (r.second, t.second) is farthest pair
}
/*************/
// 頂点クエリ
/*************/
// 頂点u, vの最小共通先祖
//
// O(log n)
int getParent(int index, ll n) const {
ll ret = index;
n = min(n, (1ll << MAXLOGV) - 1);
rep(k, MAXLOGV) if (ret != -1) if (n & (1ll << k)) {
ret = parent[k][ret];
}
return ret;
}
// 頂点u, vの最小共通先祖
//
// O(log n)
int lca(int u, int v) const {
if (depth[u] > depth[v]) swap(u, v); // uのほうが浅くなるように
for (int k = 0; k < MAXLOGV; k++) // vをuと同じ深さまで遡る
if ((depth[v] - depth[u])>>k & 1)
v = parent[k][v];
if (u == v) return u;
for (int k = MAXLOGV-1; k >= 0; k--) { // 行き過ぎないギリギリで遡る
if (parent[k][u] == parent[k][v]) // 行き過ぎ
continue;
u = parent[k][u];
v = parent[k][v];
}
return parent[0][u];
}
// uとvの距離を求める
// 距離はエッジの重み=1としたときのもの
//
// O(log n)
int dist(int u, int v) const {
int p = lca(u, v);
return (depth[u]-depth[p]) + (depth[v]-depth[p]);
}
/*************/
// 描画
/*************/
void print_dfs(int v, int p) const {
for (int i = 0; i < depth[v]; i++)
cout << " ";
cout << v << endl;
for (edge_t next : m_edges[v]) if (next.to != p)
print_dfs(next.to, v);
}
void print(void) const {
print_dfs(root, -1);
}
};
int main(void) {
int n; cin >> n;
Tree tree(n, 0);
vector<int> as, bs;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b;
tree.unite(a, b);
as.pb(a);
bs.pb(b);
}
// tree.print();
tree.init();
vector<matrix> data(n, identity(2));
ll q; cin >> q;
rep(_, q) {
char c; cin >> c;
if (c == 'x') {
ll index; cin >> index;
int leaf_side_index = (tree.depth[as[index]] > tree.depth[bs[index]] ? as[index] : bs[index]);
matrix m = zero(2);
cin >> m[0][0] >> m[0][1] >> m[1][0] >> m[1][1];
data[leaf_side_index] = m;
} else {
ll u, v; cin >> u >> v; // u is root size
matrix m = identity(2);
while (u != v) {
m = mul(data[v], m);
v = tree.getParent(v, 1);
}
cout << m[0][0] << " " << m[0][1] << " " << m[1][0] << " " << m[1][1] << endl;
}
}
return 0;
}