結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー SSRSSSRS
提出日時 2023-05-30 16:44:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,199 ms / 10,000 ms
コード長 8,078 bytes
コンパイル時間 3,083 ms
コンパイル使用メモリ 207,148 KB
実行使用メモリ 62,584 KB
最終ジャッジ日時 2023-08-28 00:53:58
合計ジャッジ時間 25,301 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 10 ms
4,540 KB
testcase_03 AC 10 ms
5,004 KB
testcase_04 AC 9 ms
4,612 KB
testcase_05 AC 9 ms
4,536 KB
testcase_06 AC 11 ms
4,896 KB
testcase_07 AC 595 ms
50,456 KB
testcase_08 AC 604 ms
50,372 KB
testcase_09 AC 608 ms
50,488 KB
testcase_10 AC 622 ms
50,512 KB
testcase_11 AC 611 ms
50,404 KB
testcase_12 AC 608 ms
48,696 KB
testcase_13 AC 604 ms
50,356 KB
testcase_14 AC 622 ms
50,472 KB
testcase_15 AC 624 ms
48,560 KB
testcase_16 AC 617 ms
50,200 KB
testcase_17 AC 589 ms
59,136 KB
testcase_18 AC 561 ms
62,584 KB
testcase_19 AC 579 ms
58,848 KB
testcase_20 AC 572 ms
60,892 KB
testcase_21 AC 550 ms
62,212 KB
testcase_22 AC 318 ms
50,636 KB
testcase_23 AC 321 ms
50,500 KB
testcase_24 AC 331 ms
51,036 KB
testcase_25 AC 1,160 ms
51,200 KB
testcase_26 AC 1,085 ms
51,220 KB
testcase_27 AC 1,185 ms
51,224 KB
testcase_28 AC 1,199 ms
51,028 KB
testcase_29 AC 1,191 ms
48,992 KB
testcase_30 AC 355 ms
50,540 KB
testcase_31 AC 338 ms
50,844 KB
testcase_32 AC 336 ms
50,856 KB
testcase_33 AC 476 ms
50,412 KB
testcase_34 AC 471 ms
48,296 KB
testcase_35 AC 487 ms
50,372 KB
testcase_36 AC 502 ms
48,244 KB
testcase_37 AC 470 ms
50,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include "debug.h"
// #include "utils.h"

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}


struct decomp {
	int n;
	int k;
	std::vector<std::vector<int> > hen;
	decomp (int n_, int k) : n(n_ + k), k(k), hen(n) {
		for (int i = 0; i < k; i++) hen[i].push_back(i + 1), hen[i + 1].push_back(i);
	}
	void add_hen(int a, int b) {
		hen[a + k].push_back(b + k);
		hen[b + k].push_back(a + k);
	}
	std::vector<int> size;
	std::vector<int> par;
	void dfs0(int i, int prev) {
		par[i] = prev;
		if (prev != -1) hen[i].erase(std::find(hen[i].begin(), hen[i].end(), prev));
		for (auto &j : hen[i]) {
			dfs0(j, i);
			if (size[j] > size[hen[i][0]]) std::swap(j, hen[i][0]);
			size[i] += size[j];
		}
	}
	std::vector<std::vector<std::vector<int> > > kdown;
	std::vector<int> group, ord_in_hp, kth_in_hp;
	int group_cnt = 1;
	std::vector<int> path;
	std::vector<int> seq, ord;
	std::vector<int> kdown_head;
	std::vector<int> in, out;
	std::vector<std::vector<std::pair<int, int> > > down_range;
	std::vector<std::vector<int> > down_leftmost;
	int get_kdown_head(int i) {
		for (int j = 0; j < k; j++) {
			if (!hen[i].size()) return -1;
			i = hen[i][0];
		}
		return i;
	}
	void dfs1(int i) {
		path.push_back(i);
		if (i >= k) kdown[path[path.size() - (k + 1)]].push_back(std::vector<int>(path.end() - (k + 1), path.end()));
		in[i] = seq.size();
		kdown_head[i] = get_kdown_head(i);
		if (kdown_head[i] != -1) seq.push_back(kdown_head[i]);
		if (!i || i != hen[par[i]][0]) kth_in_hp[i] = kdown_head[i];
		else kth_in_hp[i] = kth_in_hp[par[i]];
		for (auto j : hen[i]) {
			if (j == hen[i][0]) ord_in_hp[j] = ord_in_hp[i] + 1, group[j] = group[i];
			else ord_in_hp[j] = 0, group[j] = group_cnt++;
			dfs1(j);
		}
		for (auto j : kdown[i]) {
			if (j.back() == kdown_head[i]) {
				for (int l = 0; l < k; l++) down_leftmost[j[l]][k - l] = j.back();
			} else {
				seq.push_back(j.back());
				for (int l = 0; l < k; l++) {
					if (down_range[j[l]][k - l].first == -1) down_range[j[l]][k - l].first = j.back();
					down_range[j[l]][k - l].second = j.back();
				}
			}
		}
		
		out[i] = seq.size();
		path.pop_back();
	}
	
	void process() {
		size.resize(n, 1);
		par.resize(n);
		dfs0(0, -1);
		ord_in_hp.resize(n);
		kth_in_hp.resize(n);
		kdown.resize(n);
		kdown_head.resize(n);
		in.resize(n);
		out.resize(n);
		group.resize(n);
		for (int i = 0; i < k; i++) seq.push_back(i);
		down_range.resize(n, std::vector<std::pair<int, int> >(k + 1, {-1, -1}));
		down_leftmost.resize(n, std::vector<int>(k + 1, -1));
		dfs1(0);
		
		assert(seq.size() == n);
		assert(std::set<int>(seq.begin(), seq.end()).size() == seq.size());
		ord.resize(n);
		for (int i = 0; i < n; i++) ord[seq[i]] = i;
		for (auto &i : down_range) for (auto &j : i) {
			if (j.first != -1) j.first = ord[j.first];
			if (j.second != -1) j.second = ord[j.second] + 1;
		}
		for (auto &i : down_leftmost) for (auto &j : i) if (j != -1) j = ord[j];
		for (int i = 0; i < n; i++) down_range[i][0] = {ord[i], ord[i] + 1};
		
		/*
		for (auto i : seq) std::cerr << i - k << " ";
		std::cerr << std::endl;
		
		for (int i = 0; i < n; i++) {
			std::cerr << i << " : " << std::endl;
			std::cerr << "  g:" << group[i] << " kth:" << kth_in_hp[i] << std::endl;
			for (int j = 1; j <= k; j++) {
				std::cerr << "  " << j << " : " << down_range[i][j].first << "," << down_range[i][j].second << " lm:" << down_leftmost[i][j] << std::endl;
			}
		}*/
	}
	std::vector<std::pair<int, int> > get_path(int x, int y) {
		x += k;
		y += k;
		std::vector<std::pair<int, int> > res;
		auto up_y = [&] () {
			res.push_back({ord[kth_in_hp[y]], ord[y] + 1});
			y = par[kth_in_hp[y]];
		};
		while (group[x] != group[y]) {
			if (group[x] > group[y]) std::swap(x, y);
			if (ord_in_hp[y] >= k) up_y();
			else {
				res.push_back({ord[y], ord[y] + 1});
				y = par[y];
			}
		}
		if (ord_in_hp[x] > ord_in_hp[y]) std::swap(x, y);
		if (ord_in_hp[y] >= k) {
			if (ord_in_hp[x] >= k) {
				res.push_back({ord[x], ord[y] + 1});
				return res;
			} else up_y();
		}
		while (y != x) {
			res.push_back({ord[y], ord[y] + 1});
			y = par[y];
		}
		res.push_back({ord[x], ord[x] + 1});
		return res;
	}
	std::vector<std::pair<int, int> > get_subtree(int x) {
		x += k;
		std::vector<std::pair<int, int> > res{{in[x], out[x]}, {ord[x], ord[x] + 1}};
		for (int i = 1; i < k; i++) {
			if (down_range[x][i].first != -1) res.push_back(down_range[x][i]);
			if (down_leftmost[x][i] != -1) res.push_back({down_leftmost[x][i], down_leftmost[x][i] + 1});
		}
		return res;
	}
	std::vector<std::pair<int, int> > get_k_vicinity(int x, int d) {
		x += k;
		assert(d <= k);
		std::vector<std::pair<int, int> > res;
		int t = x;
		int depth = d;
		for (int i = d; i >= -d; i--, depth--) {
			if (i != d && !((d - i) & 1)) t = par[t], depth++;
			// std::cerr << " depth " << i << " : " << t << "@" << depth << std::endl;
			if (down_range[t][depth].first != -1) res.push_back(down_range[t][depth]);
			if (down_leftmost[t][depth] != -1) res.push_back({down_leftmost[t][depth], down_leftmost[t][depth] + 1});
		}
		return res;
	}
	int pos(int x) { return ord[x + k]; }
};

template<class monoid_t> struct dual_segtree {
	using value_t = decltype(monoid_t::unit());
	static_assert(std::is_same<decltype(monoid_t::op), value_t(value_t, value_t)>::value ||
				  std::is_same<decltype(monoid_t::op), value_t(const value_t &, const value_t &)>::value, "");
	value_t unit() { return monoid_t::unit(); }
	int n_, n;
	std::vector<value_t> vals;
	
	int ceil_power2(int x) { int i = 1; while (i < x) i <<= 1; return i; }
	dual_segtree (int n_) : n_(n_), n(ceil_power2(n_)), vals(n << 1, unit()) {}
	template<typename itr_t> dual_segtree (itr_t begin, itr_t end) : dual_segtree(end - begin) {
		std::copy(begin, end, vals.begin() + n);
	}
	template<typename T = value_t> dual_segtree (const std::vector<T> &a) : dual_segtree(a.begin(), a.end()) {}
	
	void flush(int i) {
		vals[i << 1] = monoid_t::op(vals[i << 1], vals[i]);
		vals[i << 1 | 1] = monoid_t::op(vals[i << 1 | 1], vals[i]);
		vals[i] = unit();
	}
	template<class func_t> void dive_range(int l, int r, int node, int nodel, int noder, const func_t &f) {
		if (r <= nodel || l >= noder) return;
		if (l <= nodel && r >= noder) f(node);
		else {
			flush(node);
			int nodem = nodel + ((noder - nodel) >> 1);
			dive_range(l, r, node << 1, nodel, nodem, f);
			dive_range(l, r, node << 1 | 1, nodem, noder, f);
		}
	}
	void apply(int l, int r, const value_t &op) {
		/// std::cerr << l << " " << r << " " << op.first << " " << op.second << std::endl;
		dive_range(l, r, 1, 0, n, [&] (int node) { vals[node] = monoid_t::op(vals[node], op); });
	}
	value_t operator [] (int i) {
		value_t res;
		dive_range(i, i + 1, 1, 0, n, [&] (int node) { res = vals[node]; });
		return res;
	}
};
template<int MOD> struct affine_mod {
	using T = std::pair<int, int>;
	using u64 = uint64_t;
	static T unit() { return {1, 0}; }
	static T op(T lhs, T rhs) { return {(u64) lhs.first * rhs.first % MOD, ((u64) lhs.second * rhs.first + rhs.second) % MOD}; }
};


#define MOD 998244353

int main() {
	int n = ri();
	int q = ri();
	decomp tree(n, 10);
	for (int i = 1; i < n; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		tree.add_hen(a, b);
	}
	tree.process();
	
	std::vector<int> a(n);
	for (auto &i : a) i = ri();
	
	dual_segtree<affine_mod<MOD> > seq(tree.n);
	for (int i = 0; i < q; i++) {
		int t = ri();
		if (t == 4) {
			int x = ri() - 1;
			int y = ri() - 1;
			int c = ri();
			int d = ri();
			for (auto j : tree.get_path(x, y)) seq.apply(j.first, j.second, {c, d});
		} else if (t == 3) {
			int x = ri() - 1;
			int c = ri();
			int d = ri();
			for (auto j : tree.get_subtree(x)) seq.apply(j.first, j.second, {c, d});
		} else if (t == 2) {
			int x = ri() - 1;
			int k = ri();
			int c = ri();
			int d = ri();
			for (auto j : tree.get_k_vicinity(x, k)) seq.apply(j.first, j.second, {c, d});
		} else {
			int x = ri() - 1;
			auto t = seq[tree.pos(x)];
			printf("%d\n", (int) (((uint64_t) a[x] * t.first + t.second) % MOD));
		}
	}
	
	return 0;
}
0