結果

問題 No.235 めぐるはめぐる (5)
ユーザー noshi91noshi91
提出日時 2018-03-17 17:41:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 670 ms / 10,000 ms
コード長 9,607 bytes
コンパイル時間 924 ms
コンパイル使用メモリ 88,136 KB
実行使用メモリ 20,016 KB
最終ジャッジ日時 2024-06-06 10:01:28
合計ジャッジ時間 3,916 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 670 ms
19,968 KB
testcase_01 AC 299 ms
20,016 KB
testcase_02 AC 589 ms
19,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
static constexpr double PI = 3.1415926535897932;

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;

void yes(bool c) { puts(c ? "yes" : "no"); }
void Yes(bool c) { puts(c ? "Yes" : "No"); }
void YES(bool c) { puts(c ? "YES" : "NO"); }
void pos(bool c) { puts(c ? "possible" : "impossible"); }
void Pos(bool c) { puts(c ? "Possible" : "Impossible"); }
void POS(bool c) { puts(c ? "POSSIBLE" : "IMPOSSIBLE"); }
template<class T>bool bmaxi(T&a, const T&b) { if (b<a)return 0;a = b;return 1; }
template<class T>bool bmini(T&a, const T&b) { if (a<b)return 0;a = b;return 1; }
template<class T>bool nmaxi(T&a, const T&b) { if (a<b) { a = b;return 1; }return 0; }
template<class T>bool nmini(T&a, const T&b) { if (b<a) { a = b;return 1; }return 0; }
template<typename T>auto scan(T&d)->typename std::enable_if<std::is_same<T, std::string
>::value>::type {
	d.clear();int c = fgetc(stdin);while (c<'a' || 'z'<c)c = fgetc(stdin);
	while ('a' <= c&&c <= 'z') { d.push_back(c);c = fgetc(stdin); }
}
template <typename T>auto scan(T&d)->
typename std::enable_if<std::is_same<T, double>::value>::type {
	scanf("%lf", &d);
}
template <typename T>auto scan(T&d)->typename std::enable_if<std::is_signed<T>::value
	== std::is_same<T, std::string>::value>::type {
	d = 0;int c = fgetc(stdin);
	while (c<'0' || '9'<c)c = fgetc(stdin);while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }
}
template <typename T>auto scan(T&d)->typename std::enable_if<std::is_signed<T>::value
	!= std::is_same<T, double>::value>::type {
	d = 0;int c = fgetc(stdin);bool f = 0;while (c<'0' || '9'<c)
	{
		if (c == '-')f = 1;c = fgetc(stdin);
	}while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }if (f)d = -d;
}
template<typename F, typename...R>void scan(F&f, R&...r) { scan(f);scan(r...); }

#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();
		n->expose(node::nil);
		n->splay();
		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;
	}
};
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;
}();
#include<cstdint>

template<std::uint_fast32_t MOD>
struct modint {
	using uint32 = std::uint_fast32_t;
	using uint64 = std::uint_fast64_t;
	uint32 a;
	modint() :a(0) {}
	modint(std::int_fast64_t x) :a(norms(x%MOD + MOD)) {}
	static uint32 norms(const uint32 &x) { return(x<MOD) ? x : x - MOD; }
	static modint make(const uint32 &x) { modint ret;ret.a = x;return ret; }
	modint operator+(const modint &o)const { return make(norms(a + o.a)); }
	modint operator-(const modint &o)const { return make(norms(a + MOD - o.a)); }
	modint operator*(const modint &o)const { return make((uint64)a*o.a%MOD); }
	modint operator/(const modint &o)const { return make((uint64)a*~o%MOD); }
	modint &operator+=(const modint &o) { return *this = *this + o; }
	modint &operator-=(const modint &o) { return *this = *this - o; }
	modint &operator*=(const modint &o) { return *this = *this * o; }
	modint &operator/=(const modint &o) { return *this = *this / o; }
	modint &operator^=(const uint32 &o) { return *this = *this^o; }
	modint operator~ ()const { return *this ^ (MOD - 2); }
	modint operator- ()const { return make(norms(MOD - a)); }
	modint operator++() { return *this = make(norms(a + 1)); }
	modint operator--() { return *this = make(norms(a + MOD - 1)); }
	bool operator==(const modint &o)const { return a == o.a; }
	bool operator!=(const modint &o)const { return a != o.a; }
	bool operator< (const modint &o)const { return a <  o.a; }
	bool operator<=(const modint &o)const { return a <= o.a; }
	bool operator> (const modint &o)const { return a >  o.a; }
	bool operator>=(const modint &o)const { return a >= o.a; }
	explicit operator bool()const { return a; }
	explicit operator uint32()const { return a; }
	modint operator^(uint32 x)const {
		uint64 t = (uint64)a;uint64 u = 1;
		while (x) { if (x & 1) u = u*t%MOD;t = (t*t) % MOD;x >>= 1; }
		return make((uint32)u);
	}
	/*
	friend std::istream &operator>>(std::istream &is, modint<MOD> &o) {
	std::int_fast64_t x;is >> x;o = modint<MOD>(x);return(is);
	}
	friend std::ostream &operator<<(std::ostream &os, const modint<MOD> &o) { return os << o.a; }
	*/
};
using mint = modint<1000000007>;
struct p {
	mint z;
	p(mint x=0):z(x){}
	p operator*(const p &o)const {
		return p(z + o.z);
	}
};
struct m {
	mint s, c;
	m(mint x=0,mint y=0):s(x),c(y){}
	m operator~()const { return *this; }
	m operator+(const m &o)const { return m(s + o.s, c + o.c); }
	m operator*(const p &o)const { return m(s + c*o.z, c); }
};

int main(void) {
	uint32 n;
	scan(n);
	std::vector<m> d(n);
	for (uint32 i = 0;i < n;++i) scan(d[i].s.a);
	for (uint32 i = 0;i < n;++i) scan(d[i].c.a);
	LC<m, p> T(d);
	uint32 a, b,c;
	while(--n){
		scan(a, b);
		T.link(a-1, b-1);
	}
	scan(n);
	mint z;
	while (n--) {
		scan(c, a, b);
		if (c) {
			printf("%u\n", T.path(a - 1, b - 1).s.a);
		}
		else {
			scan(z.a);
			T.update(a - 1, b - 1, p(z));
		}
	}
	return 0;
}
0