結果

問題 No.235 めぐるはめぐる (5)
ユーザー noshi91noshi91
提出日時 2018-03-17 17:25:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,003 ms / 10,000 ms
コード長 6,465 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 100,484 KB
実行使用メモリ 20,480 KB
最終ジャッジ日時 2024-06-06 10:00:42
合計ジャッジ時間 5,787 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,003 ms
20,364 KB
testcase_01 AC 468 ms
20,480 KB
testcase_02 AC 891 ms
20,292 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;

#include <cassert>
#include <cstdint>
#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 Mo, typename Op> class LC {
	struct node {
		node *left, *right, *per;
		Mo data, sum;
		Op lazy;
		bool isroot, rev;
		static node *const nil;
		void push() {
			if (rev) {
				left->rev ^= 1;
				right->rev ^= 1;
				std::swap(left, right);
				data = ~data;
				rev = 0;
			}
			data = data * lazy;
			left->lazy = left->lazy * lazy;
			right->lazy = right->lazy * lazy;
			lazy = Op();
		}
		Mo reflect() const { return rev ? ~sum * lazy : sum * lazy; }
		void fix() {
			if (rev)
				sum = ~sum;
			sum = sum * lazy;
			push();
		}
		void propagate() {
			if (per)
				per->propagate();
			push();
		}
		void haulL(node *const l) {
			left = l;
			l->per = this;
		}
		void haulR(node *const r) {
			right = r;
			r->per = this;
		}
		void splay() {
			node *x = this, *pp = per;
			left->fix();
			right->fix();
			nil->sum = Mo();
			nil->lazy = Op();
			nil->rev = 0;
			while (!x->isroot) {
				if (pp) {
					if (pp->left == x)
						pp->left = this;
					else
						pp->right = this;
				}
				if (per->isroot) {
					if (per->left == this) {
						per->haulL(right);
						per->sum = right->sum + per->data + per->right->reflect();
						right = per;
						x = per;
						per = per->per;
						right->per = this;
					}
					else {
						per->haulR(left);
						per->sum = per->left->reflect() + per->data + left->sum;
						left = per;
						x = per;
						per = per->per;
						left->per = this;
					}
					break;
				}
				x = per->per;
				pp = x->per;
				if (per->left == this) {
					if (x->left == per) {
						x->haulL(per->right);
						x->sum = x->left->reflect() + x->data + x->right->reflect();
						per->haulR(x);
						per->haulL(right);
						per->sum = right->sum + per->data + x->sum;
						haulR(per);
					}
					else {
						x->haulR(left);
						x->sum = x->left->reflect() + x->data + left->sum;
						per->haulL(right);
						per->sum = right->sum + per->data + per->right->reflect();
						haulL(x);
						haulR(per);
					}
				}
				else {
					if (x->right == per) {
						x->haulR(per->left);
						x->sum = x->left->reflect() + x->data + x->right->reflect();
						per->haulL(x);
						per->haulR(left);
						per->sum = x->sum + per->data + left->sum;
						haulL(per);
					}
					else {
						x->haulL(right);
						x->sum = right->sum + x->data + x->right->reflect();
						per->haulR(left);
						per->sum = per->left->reflect() + per->data + left->sum;
						haulR(x);
						haulL(per);
					}
				}
				per = pp;
			}
			sum = left->sum + data + right->sum;
			x->isroot = 0;
		}
		void expose(node *const prev) {
			splay();
			if (right != nil)
				right->isroot = 1;
			right = prev;
			sum = left->sum + data + right->sum;
			if (per)
				per->expose(this);
			else
				isroot = 1;
		}
	};
	std::vector<node> tree;
	void expose(node *const n) {
		n->propagate();
		scan();
		n->expose(node::nil);
		scan();
		n->splay();
		scan();
		n->isroot = 1;
		n->sum = n->left->sum + n->data + n->right->sum;
	}

public:
	LC(const uint32 size)
		: tree(size, { node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0 }) {}
	LC(const std::vector<Mo> &a)
		: tree(a.size(),
		{ node::nil, node::nil, nullptr, Mo(), Mo(), Op(), 1, 0 }) {
		for (uint32 i = 0; i < a.size(); ++i)
			tree[i].data = tree[i].sum = a[i];
	}
	void link(uint32 child, uint32 per) {
		evert(child);
		tree[child].per = &tree[per];
	}
	void cut(uint32 child) {
		node *n = &tree[child];
		expose(n);
		n->left->per = nullptr;
		n->left->isroot = 1;
		n->left = node::nil;
		n->sum = n->data;
	}
	void update(uint32 u, uint32 v, const Op &data) {
		evert(u);
		expose(&tree[v]);
		tree[v].lazy = data;
	}
	Mo path(uint32 u, uint32 v) {
		evert(u);
		expose(&tree[v]);
		return tree[v].sum;
	}
	void evert(uint32 v) {
		expose(&tree[v]);
		tree[v].rev ^= 1;
	}
	//*
	struct vis {
	int32 l, r, p, rev;
	};
	std::vector<vis> v;
	int32 ch(node *n) {
	if (n==node::nil) return -9;
	return n - &tree[0];
	}
	void scan(void) {
	return;
	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].rev };
	}
	}
	//*/
};
template <typename Mo, typename Op>
typename LC<Mo, Op>::node *const LC<Mo, Op>::node::nil = []() {
	LC<Mo, Op>::node *const ret = new LC<Mo, Op>::node;
	ret->left = ret->right = ret;
	ret->data = ret->sum = Mo();
	return ret;
}();
static constexpr uint64 MOD = 1000000007;
struct p {
	uint64 data;
	p(uint64 x=0) :data(x) {}
	p operator*(const p &other)const {
		return p((data + other.data) % MOD);
	}
};
struct meguru {
	uint64 s, c;
	meguru() :s(0), c(0) {}
	meguru(uint64 x, uint64 y) :s(x), c(y) {}
	meguru operator~()const {
		return *this;
	}
	meguru operator+(const meguru &other)const {
		return meguru((s + other.s) % MOD, (c + other.c) % MOD);
	}
	meguru operator*(const p &other)const {
		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;
	}
	LC<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--) {
		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));
		}
		L.scan();
	}
	return 0;
}
0