結果

問題 No.650 行列木クエリ
コンテスト
ユーザー shobonvip
提出日時 2024-10-05 20:03:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 119 ms / 2,000 ms
コード長 4,120 bytes
コンパイル時間 3,887 ms
コンパイル使用メモリ 267,832 KB
実行使用メモリ 37,908 KB
最終ジャッジ日時 2024-10-05 20:03:31
合計ジャッジ時間 5,483 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

struct HLDecomposition {
	private:
		void make_child(int i, int p) {
			for (int j: ikeru[i]){
				if (j == p) continue;
				dep[j] = dep[i] + 1;
				child[i].push_back(j);
				par[j] = i;
				make_child(j, i);
			}
		}

		void dfs_siz(int i) {
			siz[i] = 1;
			for (int &j: child[i]) {
				dfs_siz(j);
				siz[i] += siz[j];
				if (siz[j] > siz[child[i][0]]) {
					std::swap(j, child[i][0]);
				}
			}
		}

		void dfs_hld(int i) {
			in[i] = cnt++;
			for (int j: child[i]) {
				if (j == child[i][0]) {
					nxt[j] = nxt[i];
				} else {
					nxt[j] = j;
				}
				dfs_hld(j);
			}
			out[i] = cnt;
		}

		// [u, v)
		std::vector<std::pair<int,int>> ascend(int u, int v) {
			std::vector<std::pair<int,int>> ret;
			while (nxt[u] != nxt[v]) {
				ret.push_back(std::pair(in[nxt[u]], in[u]+1));
				u = par[nxt[u]];
			}
			if (u == v) return ret;
			ret.push_back(std::pair(in[v]+1, in[u]+1));
			return ret;
		}

	public:
		int n, root, cnt;
		std::vector<std::vector<int>> ikeru, child;
		std::vector<int> siz, in, out, nxt, dep, par;
		
		HLDecomposition(int _n, int _root = 0): n(_n), root(_root) {
			cnt = 0;
			siz.resize(n);
			in.resize(n);
			out.resize(n);
			nxt.resize(n);
			dep.resize(n);
			par.resize(n);
			std::fill(par.begin(), par.end(), -1);
			ikeru.resize(n);
			child.resize(n);
		}

		void add_edge(int u, int v) {
			ikeru[u].push_back(v);
			ikeru[v].push_back(u);
		}

		void build() {
			make_child(root, -1);
			dfs_siz(root);
			nxt[root] = root;
			dfs_hld(root);
		}

		int lca(int u, int v) {
			while (nxt[u] != nxt[v]) {
				if (in[nxt[u]] < in[nxt[v]]) {
					std::swap(u, v);
				}
				u = par[nxt[u]];
			}
			if (in[u] > in[v]) {
				return v;
			} else {
				return u;
			}
		}

		// f(int left, int right, bool reverse)
		template <class F>
		void path_query(int u, int v, bool vertex_mode, const F &f) {
			int l = lca(u, v);
			std::vector<std::pair<int,int>> u_to_l = ascend(u, l); 
			std::vector<std::pair<int,int>> l_to_v = ascend(v, l);
			std::reverse(l_to_v.begin(), l_to_v.end());
			for (auto [a, b]: u_to_l) f(a, b, true);
			if (vertex_mode) f(in[l], in[l] + 1, false);
			for (auto [a, b]: l_to_v) f(a, b, false);
		}

		template <class F>
		void subtree_query(int i, bool vertex_mode, const F &f) {
			f(in[i] + int(!vertex_mode), out[i]);
		}
};

using namespace std;
typedef long long ll;
#include<atcoder/modint>
#include<atcoder/segtree>
typedef atcoder::modint1000000007 mint;

struct S {
	mint v[2][2];
};

S e(){
	S ret;
	ret.v[0][0] = 1;
	ret.v[0][1] = 0;
	ret.v[1][0] = 0;
	ret.v[1][1] = 1;
	return ret;
}

S op(S a, S b){
	S ret;
	ret.v[0][0] = 0;
	ret.v[0][1] = 0;
	ret.v[1][0] = 0;
	ret.v[1][1] = 0;
	for (int i=0; i<2; i++){
		for (int j=0; j<2; j++){
			for (int k=0; k<2; k++){
				ret.v[i][j] += a.v[i][k] * b.v[k][j];
			}
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	HLDecomposition hld(n);

	vector<int> a(n-1), b(n-1);
	for (int i=0; i<n-1; i++){
		int u, v; 
		cin >> u >> v;
		a[i] = u;
		b[i] = v;
		hld.add_edge(u, v);
	}

	hld.build();

	atcoder::segtree<S,op,e> seg_pos(n);
	atcoder::segtree<S,op,e> seg_neg(n);
	
	S tmp;
	auto f = [&](int l, int r, bool rev) -> void {
		if (!rev) {
			tmp = op(tmp, seg_pos.prod(l, r));
		}else{
			tmp = op(tmp, seg_neg.prod(l, r));
		}
	};

	auto query = [&](int u, int v) -> S {
		tmp = e();
		hld.path_query(u, v, false, f);
		return tmp;
	};

	int q; cin >> q;
	while(q--){
		char c; cin >> c;
		if (c == 'x') {
			int i; cin >> i;
			int x00, x01, x10, x11;
			cin >> x00 >> x01 >> x10 >> x11;
			S tmp;
			tmp.v[0][0] = x00;
			tmp.v[0][1] = x01;
			tmp.v[1][0] = x10;
			tmp.v[1][1] = x11;
			if (a[i] == hld.par[b[i]]){
				seg_pos.set(hld.in[b[i]], tmp);
				seg_neg.set(n-1-hld.in[b[i]], tmp);
			}else{
				seg_pos.set(hld.in[a[i]], tmp);
				seg_neg.set(n-1-hld.in[a[i]], tmp);
			}
		} else {
			int i, j; cin >> i >> j;
			S f = query(i, j);
			cout << f.v[0][0].val() << ' ';
			cout << f.v[0][1].val() << ' ';
			cout << f.v[1][0].val() << ' ';
			cout << f.v[1][1].val() << '\n';
		}	
	}

	
}
0