結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2018-02-09 23:13:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 526 ms / 2,000 ms |
コード長 | 6,675 bytes |
コンパイル時間 | 1,507 ms |
コンパイル使用メモリ | 105,620 KB |
実行使用メモリ | 61,528 KB |
最終ジャッジ日時 | 2024-10-09 09:00:11 |
合計ジャッジ時間 | 4,589 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include<algorithm>#include<iostream>#include<functional>#include<queue>#include<vector>using namespace std;typedef long long lint;typedef vector<int>vi;typedef pair<int,int>pii;#define rep(i,n)for(int i=0;i<(int)(n);++i)/// http://pekempey.hatenablog.com/entry/2015/11/06/193123//*****************************************************************// HL Decomposition のライブラリ//*****************************************************************struct HLDecomposition {vector<vector<int> > g;// vid, head, heavy, parent は必須// depth, inv は使用する機能によっては不要vector<int> vid, head, heavy, parent, depth, inv;HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}// 辺 (u, v) を追加するvoid add(int u, int v) {g[u].push_back(v);g[v].push_back(u);}// 構築するvoid build() {dfs(0, -1);bfs();}int dfs(int curr, int prev) {parent[curr] = prev;int sub = 1, max_sub = 0;for (int next : g[curr]) if (next != prev) {depth[next] = depth[curr] + 1;int sub_next = dfs(next, curr);sub += sub_next;if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;}return sub;}void bfs() {int k = 0;queue<int> q;q.push(0);while (!q.empty()) {int h = q.front(); q.pop();for (int i = h; i != -1; i = heavy[i]) {vid[i] = k++;inv[vid[i]] = i;head[i] = h;for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);}}}// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// 以下の関数は必要に応じて実装// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// 頂点属性の for_eachvoid for_each(int u, int v, function<void(int, int)> f) {if (vid[u] > vid[v]) swap(u, v);f(max(vid[head[v]], vid[u]), vid[v]);if (head[u] != head[v]) for_each(u, parent[head[v]], f);}// 頂点属性の for_each (有向// fの3番目の引数には順方向なら0、逆方向なら1が渡されるvoid for_each_directed(int u, int v, function<void(int, int, int)> f) {if (vid[u] > vid[v]) {f(max(vid[head[u]], vid[v]), vid[u], 1);if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f);} else {f(max(vid[head[v]], vid[u]), vid[v], 0);if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f);}}// 辺属性の for_eachvoid for_each_edge(int u, int v, function<void(int, int)> f) {if (vid[u] > vid[v]) swap(u, v);if (head[u] != head[v]) {f(vid[head[v]], vid[v]);for_each_edge(u, parent[head[v]], f);} else {if (u != v) f(vid[u] + 1, vid[v]);}}// 頂点 u の d 個上の頂点を求める(存在しないなら0を返す)int ancestor(int u, int d) {while (true) {if (depth[head[u]] > depth[u] - d) {d -= depth[u] - depth[head[u]] + 1;if (head[u] == 0) return 0;u = parent[head[u]];} else {return inv[vid[u] - d];}}}// 頂点 u と頂点 v の LCA を求めるint lca(int u, int v) {if (vid[u] > vid[v]) swap(u, v);if (head[u] == head[v]) return u;return lca(u, parent[head[v]]);}// 頂点 u と頂点 v の距離を求めるint distance(int u, int v) {return depth[u] + depth[v] - 2 * depth[lca(u, v)];}};// https://github.com/koba-e964/contest/blob/master/comm/SegTree.cpp/*** Segment Tree. This data structure is useful for fast folding on intervals of an array* whose elements are elements of monoid M. Note that constructing this tree requires the identity* element of M and the operation of M.* Header requirement: vector, algorithm* Verified by AtCoder ABC017-D (http://abc017.contest.atcoder.jp/submissions/660402)*/template<class I, class BiOp = I (*) (I, I)>class SegTree {int n;std::vector<I> dat;BiOp op;I e;public:SegTree(int n_, BiOp op, I e) : op(op), e(e) {n = 1;while (n < n_) { n *= 2; } // n is a power of 2dat.resize(2 * n);for (int i = 0; i < 2 * n - 1; i++) {dat[i] = e;}}/* ary[k] <- v */void update(int k, I v) {k += n - 1;dat[k] = v;while (k > 0) {k = (k - 1) / 2;dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);}}void update_array(int k, int len, const I *vals) {for (int i = 0; i < len; ++i) {update(k + i, vals[i]);}}/*Updates all elements. O(n)*/void update_all(const I *vals, int len) {for (int k = 0; k < std::min(n, len); ++k) {dat[k + n - 1] = vals[k];}for (int k = std::min(n, len); k < n; ++k) {dat[k + n - 1] = e;}for (int b = n / 2; b >= 1; b /= 2) {for (int k = 0; k < b; ++k) {dat[k + b - 1] = op(dat[k * 2 + b * 2 - 1], dat[k * 2 + b * 2]);}}}/* l,r are for simplicity */I querySub(int a, int b, int k, int l, int r) const {// [a,b) and [l,r) intersects?if (r <= a || b <= l) return e;if (a <= l && r <= b) return dat[k];I vl = querySub(a, b, 2 * k + 1, l, (l + r) / 2);I vr = querySub(a, b, 2 * k + 2, (l + r) / 2, r);return op(vl, vr);}/* [a, b] (note: inclusive) */I query(int a, int b) const {return querySub(a, b + 1, 0, 0, n);}};const lint mod=1e9+7;typedef vector<lint> vl;typedef vector<vl> mat;struct pmul{mat operator()(mat x,mat y)const{mat ret(2,vl(2));rep(i,2){rep(j,2){rep(k,2){ret[i][j]=(ret[i][j]+x[i][k]*y[k][j])%mod;}}}return ret;}};const int N=110000;vi g[N];void disp_mat(ostream &is,mat m){rep(i,4){is<<m[i/2][i%2]<<(i==3?"\n":" ");}}int main(){int n;cin>>n;mat unit(2,vl(2));vi tap(n-1),lis(n-1);unit[0][0]=unit[1][1]=1;HLDecomposition hld(n);rep(i,n-1){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);hld.add(a,b);tap[i]=a;lis[i]=b;}hld.build();SegTree<mat,pmul> st(n,pmul(),unit);int q;cin>>q;rep(_,q){string type;cin>>type;if(type=="g"){int i,j;cin>>i>>j;mat ans(unit);hld.for_each_edge(i, j, [&](int l, int r) {//cerr<<"l,r="<<l<<","<<r<<endl;ans=pmul()(st.query(l,r),ans);});disp_mat(cout,ans);}else{int i;cin>>i;int v=hld.parent[tap[i]]!=lis[i]?lis[i]:tap[i];//cerr<<"edge " << i << " vert " << v << endl;mat x(2,vl(2));rep(a,2)rep(b,2)cin>>x[a][b];hld.for_each(v, v, [&](int l, int r) {//cerr<<"updating " << l << endl;st.update(l,x);});}if(0){cerr<<"dump " << _ << endl;rep(i,n){disp_mat(cerr,st.query(i,i));}cerr<<endl;}}}