結果

問題 No.235 めぐるはめぐる (5)
ユーザー moyashi_senpaimoyashi_senpai
提出日時 2017-04-02 03:02:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 763 ms / 10,000 ms
コード長 7,243 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 147,108 KB
実行使用メモリ 89,052 KB
最終ジャッジ日時 2024-07-07 19:23:32
合計ジャッジ時間 5,880 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 763 ms
64,176 KB
testcase_01 AC 563 ms
89,052 KB
testcase_02 AC 716 ms
67,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pii Dir[8] = { //移動
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) {}
	ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};
typedef ModInt<1000000007> mint;
class Graph {
public:
	int vn;
	int sumcost = 0;
	vector<vector<pii>> g;

	Graph(int n) {
		vn = n;
		g.resize(n);
	}
	virtual void con(int a, int b, int w) = 0;
	int getWeight(int f, int t) {
		auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN));
		if (itr != g[f].end())
			return itr->second;
		return INT_MIN;
	}
	int Costsum() {
		return sumcost;
	}
};

class BiDGraph : public Graph {//無向
public:
	BiDGraph(int n) : Graph(n) {}

	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		g[b].push_back({ a, w });
		sumcost++;
	}
};
class Heavy_Light_Decomposition {
public:
	BiDGraph g, compg;
	vector<int> sz, depth, chain, par;

	int bn = 0;
	vector<int> bvn, inbn;
	vector<vector<int>> bv;

	Heavy_Light_Decomposition(BiDGraph graph, int root) :
		g(graph), compg(graph.vn), sz(graph.vn, 1), depth(graph.vn), chain(graph.vn), par(graph.vn),
		bvn(graph.vn), inbn(graph.vn) {
		getsz(root, root);
		bv.push_back(vector<int>());
		HLD(root, -1, root, 0);
	}

	int getsz(int cur, int p) {
		par[cur] = p;
		for (auto itr : g.g[cur])
			if (p != itr.first)
				depth[itr.first] = depth[cur] + 1, sz[cur] += getsz(itr.first, cur);
		return sz[cur];
	}

	void HLD(int cur, int p, int head, int num) {
		chain[cur] = head, bvn[cur] = num;
		inbn[cur] = bv[num].size(), bv[num].push_back(cur);
		pii Maxc = { -1,-1 };
		for (auto itr : g.g[cur])
			if (itr.first != p)
				Maxc = max(Maxc, { sz[itr.first], itr.first });


		for (auto itr : g.g[cur])
			if (itr.first != p) {
				int nb = num;
				if (itr.first != Maxc.second) {
					bv.push_back(vector<int>());
					nb = ++bn;
				}
				HLD(itr.first, cur, itr.first == Maxc.second ? head : itr.first, nb);
			}
	}


	int lca(int a, int b) {
		if (chain[a] == chain[b]) return depth[a] < depth[b] ? a : b;
		if (depth[chain[a]] > depth[chain[b]])
			return lca(par[chain[a]], b);
		return lca(a, par[chain[b]]);
	}

	void for_each_edge(int a, int b, function<void(int, int)> func) {
		if (chain[a] == chain[b]) return func(inbn[a] < inbn[b] ? a: b, inbn[a] < inbn[b] ?b:a);
		if (depth[chain[a]] < depth[chain[b]]) swap(a,b);
		for_each_edge(a, chain[a], func),for_each_edge(par[chain[a]], b, func);
	}
};


template<typename T>
class Lazy_Segment_Tree {//0-indexed 半開
public:
	vector<T> data, lazy;
	vector<mint> rui;
	int n;
	Lazy_Segment_Tree(int a, vector<mint> &ru) :n(1), rui(ru) {
		while (n < a) n *= 2;
		data.resize(n * 2 - 1);
		lazy.resize(n * 2 - 1);
	}

	void add(int a, int b, T ad, int noluz = 0, int num = 0, int base = 1) {
		int l = (num + 1 - base) * (n / base), r = l + n / base;
		if (a == l && b == r && !noluz)
			lazy[num] += ad;
		else if (r - l == 1)
			data[num] += ad;
		else {
			if (noluz)
				data[num] += ad*(b - a);
			else
				data[num] += ad*(rui[b] - rui[a]);

			int nr = (l + r) / 2;
			if (nr > a) add(a, min(b, nr), ad, noluz, num * 2 + 1, base * 2);
			if (nr < b) add(max(a, nr), b, ad, noluz, num * 2 + 2, base * 2);
		}
	}

	T sum(int a, int b, int num = 0, int base = 1) {
		int l = (num + 1 - base) * (n / base), r = l + n / base;
		data[num] += lazy[num] * (rui[min((int)rui.size()-1,r)] - rui[l]);
		if (num < n - 1) lazy[num * 2 + 1] += lazy[num], lazy[num * 2 + 2] += lazy[num];
		lazy[num] = T();
		if (a == l && b == r)
			return data[num];
		else {
			int nr = (l + r) / 2;
			T ret = T();
			if (nr > a) ret += sum(a, min(b, nr), num * 2 + 1, base * 2);
			if (nr < b) ret += sum(max(a, nr), b, num * 2 + 2, base * 2);
			return ret;
		}
	}
};




signed main() {
	int n, m;
	scnaf("%d", &n);
	BiDGraph g(n);
	vector<int> cos(n), kei(n);
	REP(i, n)
		scnaf("%d", &cos[i]);
	REP(i, n)
		scnaf("%d", &kei[i]);

	REP(i, n - 1) {
		int a, b;
		scanf("%d %d", &a, &b);
		g.con(--a, --b);
	}

	Heavy_Light_Decomposition hld(g, 0);

	vector<Lazy_Segment_Tree<mint>> seg;
	vector<vector<mint>> rui(hld.bv.size());
	REP(i, hld.bv.size()) {
		rui[i].resize(hld.bv[i].size() + 1);
		REP(j, (int)hld.bv[i].size())
			rui[i][j + 1] += kei[hld.bv[i][j]], rui[i][j+1] += rui[i][j];
		seg.push_back(Lazy_Segment_Tree<mint>(hld.bv[i].size(), rui[i]));
		REP(j, hld.bv[i].size())
			seg[i].add(j, j + 1, cos[hld.bv[i][j]], 1);
	}
	scanf("%d", &m);
	REP(i, m) {
		int mode;
		scnaf("%d", &mode);
		if (mode) {
			int a, b;
			scanf("%d %d", &a, &b);
			a--, b--;
			mint ans = 0;
			hld.for_each_edge(a, b, [&](int u, int v) {
				ans += seg[hld.bvn[u]].sum(hld.inbn[u], hld.inbn[v] + 1);
			});
			pritnf("%d\n", ans.get());
		}
		else {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			a--, b--;
			hld.for_each_edge(a, b, [&](int u, int v) {
				seg[hld.bvn[u]].add(hld.inbn[u], hld.inbn[v] + 1, c);
			});
		}
	}

	return 0;
}
0