結果
問題 |
No.650 行列木クエリ
|
ユーザー |
|
提出日時 | 2025-09-05 13:25:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 4,788 bytes |
コンパイル時間 | 3,865 ms |
コンパイル使用メモリ | 306,856 KB |
実行使用メモリ | 34,596 KB |
最終ジャッジ日時 | 2025-09-05 13:25:43 |
合計ジャッジ時間 | 5,362 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i< (n); ++i) #define repi(i, a, b) for (int i = (a); i < (b); ++i) #define all(x) (x).begin(), (x).end() #define fore(i, a) for(auto &i:a) using ll = long long; #include<atcoder/modint> using namespace atcoder; using mint = modint1000000007; #include<atcoder/lazysegtree> class HLdecomposition{ private: int V; vector<vector<int> > G; vector<int> stsize, parent, pathtop, in, out; int root; void BuildStsize(int u, int p){ stsize[u] = 1, parent[u] = p; for(int& v : G[u]){ if(v == p){ if(v == G[u].back()) break; else swap(v, G[u].back()); } BuildStsize(v, u); stsize[u] += stsize[v]; if(stsize[v] > stsize[G[u][0]]){ swap(v, G[u][0]); } } } void BuildPath(int u, int p, int& tm){ in[u] = tm++; for(int v : G[u]){ if(v == p) continue; pathtop[v] = (v == G[u][0] ? pathtop[u] : v); BuildPath(v, u, tm); } out[u] = tm; } public: int getter(int u){ return in[u]; } void add_edge(int u, int v){ G[u].push_back(v), G[v].push_back(u); } void build(int _root=0){ root = _root; int tm = 0; BuildStsize(root, -1); pathtop[root] = root; BuildPath(root, -1, tm); } //元の頂点のインデックスの配列上でのidを返す inline int get(int a){ return in[a]; } int lca(int a, int b){ int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ a = parent[pa], pa = pathtop[a]; }else{ b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); return a; } void subtree_query(int a, const function< void(int, int) > &func){ func(in[a], out[a]); } // 例: hl.path_query(q, r, [&](int l, int r){ seg.range(l, r, s); }) // 例: hl.query(q, r, [&](int l, int r){ ans += seg.query(l, r); }) void path_query(int a, int b, const function< void(int, int) > &func, bool is_prod){ int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ func(in[pa], in[a] + 1); a = parent[pa], pa = pathtop[a]; }else{ func(in[pb], in[b] + 1); b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); func(in[a]+(is_prod?1:0), in[b] + 1); } HLdecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1), pathtop(V, -1), in(V, -1), out(V, -1){} }; struct S{ mint a00; mint a01; mint a10; mint a11; }; S op(S a, S b){ return S{a.a00*b.a00+a.a01*b.a10, a.a00*b.a01+a.a01*b.a11, a.a10*b.a00+a.a11*b.a10, a.a10*b.a01+a.a11*b.a11}; } S e(){ mint e00, e01, e10, e11; e00 = 1;e01 = 0;e10 = 0;e11 = 1; return S{e00, e01, e10, e11}; } struct F{ mint a00; mint a01; mint a10; mint a11; bool flag; }; S mapping(F f, S x){ if(f.flag) return S{f.a00,f.a01,f.a10,f.a11}; else return x; } F composition(F f, F g){ if(f.flag) return f; else return g; }; F id(){ mint e00, e01, e10, e11; e00 = -1;e01 = -1;e10 = -1; e11 = -1; return F{e00, e01,e10,e11, false}; } int main() { ll n; cin >> n; HLdecomposition HLD(n); ll a, b; vector<pair<ll,ll>> edges(n-1); rep(i, n-1){ cin >> a >> b; edges[i] = {a, b}; HLD.add_edge(a, b); } HLD.build(); ll q;cin >> q; vector<tuple<char,ll,ll,ll,ll,ll>> qs(q); char t; ll k, j, x00, x01, x10, x11; rep(qq, q){ cin >> t; if(t == 'x'){ cin >> k >> x00 >> x01 >> x10 >> x11; qs[qq] = {t,k,x00,x01,x10,x11}; } if(t == 'g'){ cin >> k >> j; qs[qq] = {t, k, j, -1, -1, -1}; } } vector<S> vec(2*n, S{1, 0, 0, 1}); lazy_segtree<S,op,e,F,mapping,composition, id> seg(vec); rep(qq, q){ auto[tt, c, d, e, f, h] = qs[qq]; if(tt == 'x'){ auto[aa, bb] = edges[c]; if(HLD.getter(aa) > HLD.getter(bb))swap(aa, bb); auto ff = [&](int l, int r){ seg.apply(l, r, F{(mint)d, (mint)e, (mint)f, (mint)h, true}); }; HLD.path_query(bb, bb, ff, false); } else{ S ans = {1, 0, 0, 1}; auto ff = [&](int l, int r){ ans = op(seg.prod(l, r), ans); }; HLD.path_query(c, d, ff,true); cout << ans.a00.val() << " " << ans.a01.val() <<" " << ans.a10.val() << " " << ans.a11.val() << endl;; } } }