結果

問題 No.650 行列木クエリ
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-02-09 23:13:37
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 570 ms / 2,000 ms
コード長 6,675 bytes
コンパイル時間 1,880 ms
コンパイル使用メモリ 104,964 KB
実行使用メモリ 61,440 KB
最終ジャッジ日時 2024-04-17 15:01:44
合計ジャッジ時間 4,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,144 KB
testcase_01 AC 319 ms
18,048 KB
testcase_02 AC 554 ms
56,704 KB
testcase_03 AC 4 ms
6,272 KB
testcase_04 AC 332 ms
18,176 KB
testcase_05 AC 570 ms
56,576 KB
testcase_06 AC 4 ms
6,272 KB
testcase_07 AC 5 ms
6,144 KB
testcase_08 AC 264 ms
18,944 KB
testcase_09 AC 439 ms
61,440 KB
testcase_10 AC 4 ms
6,272 KB
権限があれば一括ダウンロードができます

ソースコード

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 （有向
	// 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_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;
    }
  }
}
0