結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_each
void 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
// f301
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_each
void 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 2
dat.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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0