結果

問題 No.650 行列木クエリ
ユーザー SHIJOUSHIJOU
提出日時 2020-09-29 00:00:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 9,654 bytes
コンパイル時間 2,892 ms
コンパイル使用メモリ 229,064 KB
実行使用メモリ 17,580 KB
最終ジャッジ日時 2024-07-02 21:04:17
合計ジャッジ時間 4,162 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 41 ms
6,944 KB
testcase_02 AC 89 ms
16,996 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 40 ms
6,940 KB
testcase_05 AC 90 ms
16,860 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 32 ms
6,944 KB
testcase_09 AC 66 ms
17,580 KB
testcase_10 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

#undef _GLIBCXX_DEBUG
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *s) {return to_string(string(s));}
string to_string(bool b) {return b?"true":"false";}
string to_string(vector<bool> v) {
	string res = "{";
	for(int i = 0; i < int(v.size()); i++) {
		if(i) res += ", ";
		res += to_string(v[i]);
	}
	res += "}";
	return res;
}
template<size_t N>
string to_string(bitset<N> v) {
	string res;
	for(size_t i = 0; i < N; i++) res += char('0' + v[i]);
	return res;
}
template<class A, class B>
string to_string(pair<A, B>);
template<class A, class B, class C>
string to_string(tuple<A, B, C>);
template<class A, class B, class C, class D>
string to_string(tuple<A, B, C, D>);
template<class A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for(const auto &x:v) {
		if(!first) res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C>
string to_string(tuple<A, B, C> t) {
	return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}
template<class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> t) {
	return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << ' ' << to_string(H);
	debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 822
#endif

const unsigned int mod = 1000000007;
//const unsigned int mod = 998244353;

struct mint {
	unsigned int x;
	mint():x(0) {}
	mint(int64_t x_) {
		int64_t v = int64_t(x_ % mod);
		if(v < 0) v += mod;
		x = (unsigned int)v;
	}
	static mint row(int v) {
		mint v_;
		v_.x = v;
		return v_;
	}
	mint operator-() const { return mint(-int64_t(x));}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		uint64_t z = x;
		z *= a.x;
		x = (unsigned int)(z % mod);
		return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
	friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
	mint &operator++() {
		x++;
		if(x == mod) x = 0;
		return *this;
	}
	mint &operator--() {
		if(x == 0) x = mod;
		x--;
		return *this;
	}
	mint operator++(int) {
		mint result = *this;
		++*this;
		return result;
	}
	mint operator--(int) {
		mint result = *this;
		--*this;
		return result;
	}
	mint pow(int64_t t) const {
		mint x_ = *this, r = 1;
		while(t) {
			if(t&1) r *= x_;
			x_ *= x_;
			t >>= 1;
		}
		return r;
	}
	//for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

template<class T>
struct SegTree {
	using FX = function<T(T, T)>;
	int n, _n;
	FX fx;
	const T ex;
	vector<T> dat;
	SegTree(int n_, FX fx_, T ex_):fx(fx_), ex(ex_), n(1), _n(n_) {
		while(n < n_) n <<= 1;
		dat.assign((n<<1)-1, ex);
	}
	SegTree(vector<T> &v, FX fx_, T ex_):fx(fx_), ex(ex_), n(1), _n(int(v.size())) {
		while(n < _n) n <<= 1;
		dat.assign((n<<1)-1, ex);
		copy(v.begin(), v.end(), dat.begin()+n-1);
		build();
	}
	inline int chld(int k) {return (k<<1)+1;}
	inline int chrd(int k) {return (k<<1)+2;}
	void set(int i, T t) {dat[i+n-1] = t;}
	void build() {
		for(int k = n-2; k >= 0; k--) dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
	}
	void update(int i, T x) {
		i += n-1;
		dat[i] = x;
		while(i) {
			i = (i-1)>>1;
			dat[i] = fx(dat[chld(i)], dat[chrd(i)]);
		}
	}
	inline T query(int a, int b) {return query(a, b, 0, 0, n);}
	T query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return ex;
		if(a <= l && r <= b) return dat[k];
		T vl = query(a, b, chld(k), l, (l+r)>>1);
		T vr = query(a, b, chrd(k), (l+r)>>1, r);
		return fx(vl, vr);
	}
	template<class F>
	int max_right(int l, F f) {
		assert(f(ex));
		if(l == _n) return _n;
		l += n;
		T now = ex;
		do {
			while(~l&1) l >>= 1;
			if(!f(fx(now, dat[l-1]))) {
				while(l < n) {
					l <<= 1;
					if(f(fx(now, dat[l-1]))) {
						now = fx(now, dat[l++ - 1]);
					}
				}
				return l-n;
			}
			now = fx(now, dat[l++ - 1]);
		} while((l & -l) != l);
		return _n;
	}
	template<class F>
	int min_left(int r, F f) {
		assert(f(ex));
		if(r == 0) return 0;
		r += n;
		T now = ex;
		do {
			r--;
			while(r > 1 and r&1) r >>= 1;
			if(!f(fx(dat[r-1], now))) {
				while(r < n) {
					r = chld(r);
					if(f(fx(dat[r-1], now))) {
						now = fx(dat[--r], now);
					}
				}
				return r+1-n;
			}
			now = fx(dat[r-1], now);
		} while((r & -r) != r);
		return 0;
	}
	const T &operator[](int idx) const {return dat[idx+n-1];}
};

struct HLD {
	using Graph = vector<vector<int>>;
	using F = function<void(int, int)>;
	Graph G;
	vector<int> parent, heavy, depth, root, ids, sub, type, inv;
	int _n;
	HLD() {}
	HLD(int n):G(n), parent(n, -1), heavy(n, -1), depth(n), root(n, -1), ids(n), _n(n), sub(n, 1), type(n), inv(n) {}

	void add(int i, int j) {
		G[i].emplace_back(j);
		G[j].emplace_back(i);
	}
	void init(vector<int> roots = vector<int>(1, 0)) {
		int group = 0;
		int pos = 0;
		for(int rt:roots) {
			dfs(rt);
			bfs(rt, group++, pos);
		}
	}
	void dfs(int rt) {
		stack<pair<int, int>> st;
		st.emplace(rt, 0);
		while(!st.empty()) {
			int v = st.top().first;
			int &siz = st.top().second;
			if(siz < int(G[v].size())) {
				int u = G[v][siz++];
				if(u == parent[v]) continue;
				parent[u] = v;
				depth[u] = depth[v]+1;
				st.emplace(u, 0);
			}
			else {
				st.pop();
				int maxSubtree = 0;
				for(int u:G[v]) {
					if(u == parent[v]) continue;
					sub[v] += sub[u];
					if(maxSubtree < sub[u]) maxSubtree = sub[u], heavy[v] = u;
				}
			}
		}
	}
	void bfs(int rt, int group, int &pos) {
		queue<int> que({rt});
		while(!que.empty()) {
			int v = que.front();
			que.pop();
			for(int u = v; u != -1; u = heavy[u]) {
				type[u] = group;
				ids[u] = pos++;
				inv[ids[u]] = u;
				root[u] = v;
				for(int w:G[u]) {
					if(w != parent[u] and w != heavy[u]) que.emplace(w);
				}
			}
		}
	}
	//edge = false -> for_each_vertex, edge = true -> for_each_edge
	void for_each(int u, int v, const F &f, bool edge = false) {
		assert(type[u] == type[v]);
		while(true) {
			if(ids[u] > ids[v]) swap(u, v);
			if(root[u] == root[v]) {
				if(edge) {
					if(u != v) f(ids[u]+1, ids[v]+1);
				}
				else f(ids[u], ids[v]+1);
				break;
			}
			f(ids[root[v]], ids[v]+1);
			v = parent[root[v]];
		}
	}
	int lca(int u, int v) {
		while(true) {
			if(ids[u] > ids[v]) swap(u, v);
			if(root[u] == root[v]) return u;
			v = parent[root[v]];
		}
	}
	int dis(int u, int v) {
		return depth[u] + depth[v] - (depth[lca(u, v)]<<1);
	}
	const int &operator[](int i) const {return ids[i];}
};

//head

struct M {
	array<array<mint, 2>, 2> x;
	M() {}
	M(mint i) {
		x[0][0] = x[1][1] = i;
	}
	M(mint a, mint b, mint c, mint d) {
		x[0][0] = a;
		x[0][1] = b;
		x[1][0] = c;
		x[1][1] = d;
	}
	M mul(const M &u) {
		M res;
		rep(i, 2) rep(j, 2) rep(k, 2) res[i][j] += x[i][k]*u[k][j];
		return res;
	}
	array<mint, 2> &operator[](int i) {return x[i];}
	const array<mint, 2> &operator[](int i) const {return x[i];}
};
ostream &operator<<(ostream &os, const M &res) {return os << res[0][0] << ' ' << res[0][1] << ' ' << res[1][0] << ' ' << res[1][1] << '\n';}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<P> ab(n-1);
	HLD hld(n);
	rep(i, n-1) {
		int a, b;
		cin >> a >> b;
		ab[i] = {a, b};
		hld.add(a, b);
	}
	hld.init();
	SegTree<M> seg(n, [](M a, M b)->M{return a.mul(b);}, M(1));
	int q;
	cin >> q;
	while(q--) {
		char c;
		cin >> c;
		if(c == 'x') {
			int id;
			mint a, b, c, d;
			cin >> id >> a >> b >> c >> d;
			auto [u, v] = ab[id];
			u = hld[u];
			v = hld[v];
			seg.update(max(u, v), M(a, b, c, d));
			debug(ab[id]);
		}
		else {
			int i, j;
			cin >> i >> j;
			M res(1);
			hld.for_each(i, j, [&](int i, int j)->void{res = seg.query(i, j).mul(res);}, true);
			cout << res;
		}
	}
}
0