結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー noshi91
提出日時 2018-04-02 13:46:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 9,623 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 93,756 KB
実行使用メモリ 26,532 KB
最終ジャッジ日時 2024-06-26 06:35:16
合計ジャッジ時間 25,162 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

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;
#include <utility>
#include <vector>

template <typename ValueMonoid, typename OperatorMonoid> class LinkCutTree {
public:
	using value_type = ValueMonoid;
	using reference = value_type &;
	using const_reference = const value_type &;
	using operator_type = OperatorMonoid;

private:
	struct node_t {
		node_t *left, *right, *per;
		value_type value, sum;
		operator_type lazy;
		bool isroot, reversed;
		static node_t *const nil;
		node_t()
			: left(nil), right(nil), per(nullptr), value(value_type()),
			sum(value_type()), lazy(operator_type()), isroot(1), reversed(0) {}
		bool isleft() const { return per->left == this; }
		value_type reflect() { return reversed ? ~(sum * lazy) : (sum * lazy); }
		void assign(const operator_type &data) { lazy = lazy * data; }
		void recalc() { sum = left->reflect() + value + right->reflect(); }
		void haulL(node_t *const t) { left = t, t->per = this; }
		void haulR(node_t *const t) { right = t, t->per = this; }
		void set(node_t *const ch) {
			if (isroot)
				ch->per = per;
			else
				isleft() ? per->haulL(ch) : per->haulR(ch);
			std::swap(isroot, ch->isroot);
		}
		void rotateL() {
			node_t *const t = per;
			t->set(this);
			t->haulR(left);
			haulL(t);
			t->recalc();
		}
		void rotateR() {
			node_t *const t = left;
			t->set(this);
			t->haulL(right);
			haulR(t);
			t->recalc();
		}
		void push() {
			left->assign(lazy);
			right->assign(lazy);
			lazy = operator_type();
			if (!reversed)
				return;
			std::swap(left, right);
			left->reversed ^= 1;
			right->reversed ^= 1;
			value = ~value;
			reversed = 0;
		}
		void propagate() {
			if (per)
				per->propagate();
			push();
		}
		void splay() {
			while (!isroot) {
				if (per->isroot) {
					isleft() ? rotateR() : rotateL();
					break;
				}
				if (isleft()) {
					if (per->isleft())
						per->rotateR(), rotateR();
					else
						rotateR(), rotateL();
				}
				else {
					if (per->isleft())
						rotateL(), rotateR();
					else
						per->rotateL(), rotateL();
				}
			}
			recalc();
		}
		void expose(node_t *const prev) {
			splay();
			right->isroot = 1;
			right = prev;
			prev->isroot = 0;
			recalc();
			if (per)
				per->expose(this);
		}
	};

public:
	using size_type = typename std::vector<node_t>::size_type;

private:
	std::vector<node_t> tree;
	void expose(node_t *const n) {
		n->propagate();
		n->expose(node_t::nil);
		n->splay();
		n->recalc();
	}
	/*
	struct vis {
	int32 l, r, p, rev;
	};
	std::vector<vis> v;
	*/
public:
	LinkCutTree(const size_type size) : tree(size) {}
	LinkCutTree(const std::vector<value_type> &a) : tree(a.size()) {
		for (uint32 i = 0; i < a.size(); ++i) {
			tree[i].value = tree[i].sum = a[i];
		}
	}
	void link(const size_type child, const size_type per) {
		evert(child);
		tree[child].per = &tree[per];
	}
	void cut(const size_type child) {
		node_t *const n = &tree[child];
		expose(n);
		n->left->per = nullptr;
		n->left->isroot = 1;
		n->left = node_t::nil;
		n->sum = n->value;
	}
	void update(const size_type u, const size_type v, const operator_type &data) {
		evert(u);
		expose(&tree[v]);
		tree[v].assign(data);
	}
	value_type path(const size_type u, const size_type v) {
		evert(u);
		expose(&tree[v]);
		return tree[v].reflect();
	}
	void evert(const size_type v) {
		expose(&tree[v]);
		tree[v].reversed ^= 1;
	}
	/*
	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 };
	}
	}
	*/
};
template <typename ValueMonoid, typename OperatorMonoid>
typename LinkCutTree<ValueMonoid, OperatorMonoid>::node_t *const
LinkCutTree<ValueMonoid, OperatorMonoid>::node_t::nil = []() {
	const auto ret = new LinkCutTree<value_type, operator_type>::node_t;
	ret->left = ret->right = ret;
	ret->per = nullptr;
	ret->value = ret->sum = value_type();
	ret->lazy = operator_type();
	ret->isroot = 0;
	ret->reversed = 0;
	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);
	LinkCutTree<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