結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 はむこ
|
| 提出日時 | 2016-09-19 23:19:40 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 629 ms / 2,000 ms |
| コード長 | 18,405 bytes |
| コンパイル時間 | 3,474 ms |
| コンパイル使用メモリ | 203,248 KB |
| 実行使用メモリ | 106,544 KB |
| 最終ジャッジ日時 | 2024-10-09 08:53:12 |
| 合計ジャッジ時間 | 7,022 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
using ll = long long; using ld = long double; using vll = vector<ll>; using vvll = vector<vll>; using vld = vector<ld>;
using vi = vector<int>; using vvi = vector<vi>;
vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }
using P = pair<ll, ll>;
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) { o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args>
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; cout << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]"; return o; }
template <typename T> ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; }
template <typename T, typename U> ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; }
template <typename T, typename U> ostream &operator<<(ostream &o, const unordered_map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]"; return o; }
void printbits(ll mask, ll n) { rep(i, n) { cout << !!(mask & (1ll << i)); } cout << endl; }
#define ldout fixed << setprecision(40)
static const long long INF = 1e18;
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) { return matrix(n, arr(n, 0)); } // 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;
}
struct Pool {
int pos;
char mem[20000000]; // 20MB
Pool(){ free(); }
template<class T>
T *fetch(size_t n = 1) {
T *res = (T*)(mem + pos);
pos += sizeof(T)*n;
return res;
}
void free(){ pos = 0; }
}; Pool pool;
template<class T>
class AssosiativeOperator {
public:
AssosiativeOperator(void) { }
T T0; // 単位元
virtual T op(T a, T b) = 0; // 結合二項演算
};
template<class T>
class AssosiativeOperatorMatrix : public AssosiativeOperator<T> {
public:
AssosiativeOperatorMatrix(void) { AssosiativeOperator<T>::T0 = identity(2); }
virtual T op(T a, T b) { return mul(a, b); }
};
template<class T>
class SegmentTree {
public:
// datのデータ構造
// 0123456789ABCDEF // インターフェースの添字
// ################
// 1--------------- // datの添字, 0は使わない！！
// 2-------3-------
// 4---5---6---7---
// 8-9-A-B-C-D-E-F-
// GHIJKLMNOPQRSTUV
// v<<1, v<<1|1は子どもたちを表している
T *dat;
AssosiativeOperator<T>* op;
int n = 1; // 確保しているサイズ！
int bits = 0; // n == 1 << bits
const size_t size_; // 確保しているサイズではない！！
int ql, qr;
SegmentTree(int n_, AssosiativeOperator<T>* op) : size_(n_) {
this->op = op;
while(n < n_) { n <<= 1; bits++; }
dat = pool.fetch<T>(n+n);
fill_n(dat, n*4, this->op->T0);
}
// 点更新
void update(int v, const T &x){
v += n;
dat[v] = x;
while (v){
v = v >> 1;
dat[v] = op->op(dat[v<<1], dat[v<<1|1]);
}
}
// 範囲クエリ
// 範囲番号nの区間[nl, nr)にop(x)を演算結果を返す
T query(int n, int nl, int nr){
// この関数は、[ql, qr)より上のノードとその子の全てにHITする
if(nr <= ql || qr <= nl) return op->T0;
if(ql <= nl && nr <= qr) return dat[n]; // 一回の区間更新に付き最大3回、した区間が小さい順にHitする。
int m = (nl + nr) / 2;
return op->op(query(n<<1, nl, m), query(n<<1|1, m, nr));
}
// [l, r)の演算結果を出力
T query(int l, int r){
ql = l; qr = r;
return query(1, 0, n);
}
};
// 静的木
//
// 構築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 = 0; // 根ノードの番号
vector<verticle_t> m_verticles;
vector<vector<verticle_t>> m_verticles_doubling; // m_verticles_doubling[i][j]: jのi^2番目の親までのm_vertivlesの結合演算opによる積分
AssosiativeOperator<verticle_t>* 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 setAssosiativeOperator(AssosiativeOperator<verticle_t>* op_init) {
op = op_init;
}
void constructDoubling(void) {
m_verticles_doubling.resize(MAXLOGV); rep(i, MAXLOGV) m_verticles_doubling[i].resize(vn);
rep(i, m_verticles_doubling.size()) rep(j, m_verticles_doubling[0].size())
m_verticles_doubling[i][j] = op->T0;
}
// 辺の構築
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]);
}
/*********/
// HL分解
/*********/
// heavy light decomposition
//
// 今までの番号を、Heavy-Lightパスの根から葉の方向へと付け替える in [0, n)
// これ自体にはデータを載せず、パスの添字のみを取得するインターフェースのみ提供
vector<int> treesize; // m_edges.size(): 子の数
// i: ノードの添字
// j: Heavy pathの添字
int hl_size = 0; // Heavy pathの数
vector<int> group; // m_edges.size(): ノードiが属するグループj
vector<int> id; // m_edges.size(): ノードiに再割り振りされた新ノード番号id in [0, m_edges.size())
vector<int> par; // hl_size: Heavy path jの根の親のノードi
vector<int> bg; // hl_size: Heavy path jの根のノードi
void setTreeSize(int v, int p) {
treesize[v]=1;
for (auto &u:m_edges[v]) if (u.to != p) {
setTreeSize(u.to, v);
treesize[v]+=treesize[u.to];
}
}
void build(int v, int p, int g, int& i) {
group[v]=g;
id[v]=i++;
if ((v == root && m_edges[v].size() == 0) || (v != root && m_edges[v].size() == 1)) return;
// 最大サイズの子hを求める
int h=-1;
for (auto &u:m_edges[v]) if (u.to != p) {
if(h == -1 || treesize[h]<treesize[u.to]) {
h=u.to;
}
}
// Heavy
build(h, v, g, i);
// Light
for (auto &u:m_edges[v]) if (u.to != p) if (h != u.to) {
par.push_back(v);
bg.push_back(i);
build(u.to, v, hl_size++, i);
}
}
void constructHLD(void) {
int n = m_edges.size();
treesize.resize(n);
group.resize(n);
id.resize(n);
setTreeSize(root, -1);
int i = 0; // 再度割り振り直す添字番号
par.push_back(-1);
bg.push_back(i);
build(root, -1, hl_size++, i);
}
// O(log n)
//
// [r, c]の再割り振りされた添字区間を返す。区間は葉から根への順番。
//
// rがcより根側のノードでなければならない
// c側から、以下の漸化式によってパスを分解する
// ret += {groupの根, c}, c = groupの根の親
using P=pair<int, int>;
vector<P> hl_decomposition(int r, int c) {
vector<P> res;
while (group[c]!=group[r]) {
res.push_back(P(bg[group[c]], id[c]));
c=par[group[c]];
}
res.push_back(P(id[r], id[c]));
return res;
}
void print_HLDecomposition(void) {
rep(i, m_edges.size()) {
cout << group[i] << " " << id[i] << endl;
}
cout << "####" << endl;
rep(i, hl_size) {
cout << par[i] << " " << bg[i] << endl;
}
}
/*************/
// 描画
/*************/
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);
}
};
/*
6
0 1
1 3
0 2
2 4
2 5
0
1 2
3 4 5
*/
int main() {
int n; cin >> n;
Tree tree(n, 0);
SegmentTree<matrix> s(n, new AssosiativeOperatorMatrix<matrix>());
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.init();
tree.constructHLD();
/*
tree.print();
cout << "HL decomposition" << endl;
tree.print_HLDecomposition();
*/
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]);
int leaf_side_hl_index = tree.id[leaf_side_index];
// cout << leaf_side_index << "#UPDATE" << endl;
matrix m = zero(2);
cin >> m[0][0] >> m[0][1] >> m[1][0] >> m[1][1];
s.update(leaf_side_hl_index, m);
} else {
ll u, v; cin >> u >> v; // u is root size
auto paths = tree.hl_decomposition(u, v);
// cout << paths << "#get" << endl;
matrix m = identity(2);
rep(i, paths.size()) {
auto&& path = paths[i];
if (i == paths.size() - 1) {
if (path.fi == path.se) break;
path.fi++;
}
m = mul(s.query(path.fi, path.se+1), m);
}
cout << m[0][0] << " " << m[0][1] << " " << m[1][0] << " " << m[1][1] << endl;
}
}
return 0;
}