結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2016-09-30 01:42:44
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 710 ms / 10,000 ms
コード長 2,886 bytes
コンパイル時間 2,120 ms
コンパイル使用メモリ 172,456 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-11-21 10:58:07
合計ジャッジ時間 5,272 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 710 ms
22,144 KB
testcase_01 AC 252 ms
22,144 KB
testcase_02 AC 607 ms
22,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;

namespace /* lctree */ {
	struct node {
		node *p, *l, *r;
		bool rev = false;
		long long val, sum, lazy = 0, w, sw;
	};

	node *create_nil() {
		node *x = new node();
		x->l = x->r = x;
		x->sw = x->sum = 0;
		return x;
	}

	node *nil = create_nil();

	node *create(int val, int w) {
		node *x = new node();
		x->p = x->l = x->r = nil;
		x->w = x->sw = w;
		x->val = val;
		x->sum = x->val;
		return x;
	}

	void fix(node *x) {
		x->sum = (x->val + x->l->sum + x->r->sum) % mod;
		x->sw = (x->w + x->l->sw + x->r->sw) % mod;
	}

	void set_rev(node *x, bool rev) {
		if (x == nil) return;
		if (rev == false) return;
		x->rev ^= rev;
	}

	void set_lazy(node *x, long long lazy) {
		if (x == nil) return;
		(x->lazy += lazy) %= mod;
		(x->sum += lazy * x->sw) %= mod;
	}

	void push(node *x) {
		set_rev(x->l, x->rev);
		set_rev(x->r, x->rev);
		set_lazy(x->l, x->lazy);
		set_lazy(x->r, x->lazy);
		if (x->rev) swap(x->l, x->r);
		(x->val += x->lazy * x->w) %= mod;
		x->rev = false;
		x->lazy = 0;
	}

	void raise(node *x) {
		node *y = x->p, *z = y->p;
		if (z->l == y) z->l = x;
		if (z->r == y) z->r = x;
		y->p = x; x->p = z;
		if (y->l == x) {
			y->l = x->r; x->r = y->l->p = y;
		} else {
			y->r = x->l; x->l = y->r->p = y;
		}
		fix(y);
	}

	bool is_root(node *x) {
		return x->p->l != x && x->p->r != x;
	}

	void splay(node *x) {
		while (!is_root(x)) {
			if (!is_root(x->p)) raise((x->p->l == x) == (x->p->p->l == x->p) ? x->p : x);
			raise(x);
		}
	}

	void push_sup(node *x) {
		if (x == nil) return;
		push_sup(x->p);
		push(x);
	}

	void expose(node *x) {
		push_sup(x);
		for (node *r = nil, *y = x; y != nil; r = y, y = y->p) {
			splay(y);
			y->r = r;
			fix(y);
		}
		splay(x);
		fix(x);
	}

	void evert(node *x) {
		expose(x);
		set_rev(x, true);
	}

	void link(node *x, node *y) {
		evert(x);
		expose(y);
		y->r = x; x->p = y;
		fix(y);
	}

	void cut(node *x) {
		expose(x);
		x->l->p = x->l = nil;
		fix(x);
	}

	node *get_path(node *x, node *y) {
		evert(x);
		expose(y);
		return y;
	}
}

#define getchar getchar_unlocked

int in() {
	int n, c;
	while ((c = getchar()) < '0') if (c == EOF) return -1;
	n = c - '0';
	while ((c = getchar()) >= '0') n = n * 10 + c - '0';
	return n;
}

int main() {
	int n;
	cin >> n;

	vector<int> S(n), C(n);
	for (int i = 0; i < n; i++) S[i] = in();
	for (int i = 0; i < n; i++) C[i] = in();

	vector<node *> tr(n);
	for (int i = 0; i < n; i++) tr[i] = create(S[i], C[i]);
	for (int i = 1; i < n; i++) link(tr[in() - 1], tr[in() - 1]);

	int q = in();
	while (q--) {
		int t = in();
		if (t == 0) {
			int u = in() - 1, v = in() - 1, z = in();
			set_lazy(get_path(tr[u], tr[v]), z);
		} else {
			int u = in() - 1, v = in() - 1;
			printf("%lld\n", get_path(tr[u], tr[v])->sum);
		}
	}
}
0