結果

問題 No.235 めぐるはめぐる (5)
ユーザー noshi91noshi91
提出日時 2018-02-24 19:17:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,037 ms / 10,000 ms
コード長 5,344 bytes
コンパイル時間 995 ms
コンパイル使用メモリ 93,904 KB
実行使用メモリ 20,444 KB
最終ジャッジ日時 2024-04-23 14:03:24
合計ジャッジ時間 5,367 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,037 ms
20,352 KB
testcase_01 AC 421 ms
20,240 KB
testcase_02 AC 914 ms
20,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <climits>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <type_traits>
#include <utility>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;

template<typename Semigroup, typename Operand>
class link_cut_tree {
	struct node_t {
		node_t *left, *right, *per;
		Semigroup value, sum;
		Operand lazy;
		std::uint_least8_t b;
		// isnotroot reverse haslazy
		node_t() :left(nullptr), right(nullptr), per(nullptr), value(Semigroup())
			, sum(Semigroup()), b(0) {}
		Semigroup reflect() {
			if (b & 1) {
				if (b & 2) return ~(sum*lazy);
				return sum*lazy;
			}
			if (b & 2) return ~sum;
			return sum;
		}
		void assign(Operand &data) {
			if (b & 1) lazy = lazy*data;
			else { lazy = data;b |= 1; }
		}
		void push() {
			if (b & 2) {
				std::swap(left, right);
				if (left) left->b ^= 2;
				if (right)right->b ^= 2;
				value = ~value;
			}
			if (b & 1) {
				value = value*lazy;
				if (left)left->assign(lazy);
				if (right) right->assign(lazy);
			}
			b &= ~3;
		}
		void propagate() {
			if (per) per->propagate();
			push();
		}
		void splay() {
			node_t *x = this, *pp;
			while (x->b & 4) {
				if (!(per->b & 4)) {
					if (per->left == this) {
						per->left = right;
						per->recalc();
						right = per;
					}
					else {
						per->right = left;
						per->recalc();
						left = per;
					}
					x = per;
					per = per->per;
					recalc();
					break;
				}
				x = per->per;
				pp = x->per;
				if (per->left == this) {
					if (x->left == per) {
						x->left = per->right;
						per->left = right;
						per->right = x;
						right = per;
					}
					else {
						x->right = left;
						per->left = right;
						right = per;
						left = x;
					}
				}
				else {
					if (x->right == per) {
						x->right = per->left;
						per->right = left;
						per->left = x;
						left = per;
					}
					else {
						x->left = right;
						per->right = left;
						left = per;
						right = x;
					}
				}
				x->recalc();
				per->recalc();
				recalc();
				per = pp;
				if (pp) {
					if (pp->left == x) {
						pp->left = this;
					}
					else if (pp->right == x) {
						pp->right = this;
					}
				}
			}
			x->b |= 4;
		}
		void expose(node_t *prev) {
			splay();
			if (right)right->b &= ~4;
			right = prev;
			recalc();
			if (per)per->expose(this);
			else  b &= ~4;
		}
		void recalc() {
			sum = value;
			if (left) {
				sum = left->reflect() + sum;
				left->per = this;
			}
			if (right) {
				sum = sum + right->reflect();
				right->per = this;
			}
		}
	};
	std::vector<node_t> tree;
	void expose(node_t *n) {
		n->propagate();
		n->expose(nullptr);
		n->splay();
		n->b &= ~4;
		n->recalc();
	}
	//*
	struct vis {
	int32 l, r, p, rev;
	};
	std::vector<vis> v;
	//*/
public:
	link_cut_tree(uint32 size) :tree(size) {}
	link_cut_tree(std::vector<Semigroup> &a) :tree(a.size()) {
		for (uint32 i = 0;i < a.size();++i) {
			tree[i].value = tree[i].sum = a[i];
		}
	}
	void link(uint32 child, uint32 per) {
		evert(child);
		tree[child].per = &tree[per];
	}
	void cut(uint32 child) {
		node_t *n = &tree[child];
		expose(n);
		if (n->left) {
			n->left->per = nullptr;
			n->left->b &= ~4;
			n->left = nullptr;
		}
		n->sum = n->value;
	}
	void update(uint32 u, uint32 v, const Operand &data) {
		evert(u);
		expose(&tree[v]);
		tree[v].lazy = data;
		tree[v].b |= 1;
	}
	Semigroup path(uint32 u, uint32 v) {
		evert(u);
		expose(&tree[v]);
		return tree[v].sum;
	}
	void evert(uint32 v) {
		expose(&tree[v]);
		tree[v].b ^= 2;
	}
	//*
	int32 ch(node_t *n) {
	if (!n) return -9;
	return n - &tree[0];
	}
	void scan(void) {
	v = std::vector<vis>(tree.size());
	for (uint32 i = 0;i < tree.size();++i) {
	v[i] = { ch(tree[i].left),ch(tree[i].right),ch(tree[i].per),tree[i].b & 2 };
	}
	}
	//*/
};
static constexpr uint64 MOD = 1000000007;
struct p {
	uint64 data;
	p(){}
	p(uint64 x) :data(x) {}
	p operator*(const p &other) {
		return p((data + other.data) % MOD);
	}
};
struct meguru {
	uint64 s, c;
	meguru(){}
	meguru(uint64 x,uint64 y):s(x),c(y){}
	meguru operator~() {
		return *this;
	}
	meguru operator+(const meguru &other) {
		return meguru((s + other.s)%MOD, (c + other.c)%MOD);
	}
	meguru operator*(const p &other) {
		return meguru((s + c*other.data) % MOD, c);
	}
};

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n;
	std::cin >> n;
	std::vector<meguru> D(n);
	uint64 s, c;
	for (uint32 i = 0;i < n;++i) {
		std::cin >> s;
		D[i].s = s;
	}
	for (uint32 i = 0;i < n;++i) {
		std::cin >> c;
		D[i].c = c;
	}
	link_cut_tree<meguru, p> L(D);
	uint32 a, b;
	for (uint32 i = 1;i < n;++i) {
		std::cin >> a >> b;
		L.link(a - 1, b - 1);
		//L.scan();
	}
	uint32 q;
	std::cin >> q;
	uint64 que, x, y, z;
	while (q--) {
		//L.scan();
		std::cin >> que >> x >> y;
		if (que) {
			std::cout << L.path(x - 1, y - 1).s << "\n";
		}
		else {
			std::cin >> z;
			L.update(x - 1, y - 1, p(z));
		}
	}
	return 0;
}
0