結果

問題 No.235 めぐるはめぐる (5)
ユーザー LuzhiledLuzhiled
提出日時 2017-07-07 10:06:17
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 5,546 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 177,532 KB
実行使用メモリ 29,860 KB
最終ジャッジ日時 2024-10-06 09:51:37
合計ジャッジ時間 6,983 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

int n;
vector<lint> s, c, v;

struct HLDecomposition {
	vector<vector<int>> g;
  vector<int> vid, head, heavy, parent, depth, inv;

	HLDecomposition(int n):g(n),vid(n,-1),head(n),heavy(n,-1),parent(n),depth(n),inv(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}

  void build() {
		dfs(0, -1);
		bfs();
	}

	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			depth[next] = depth[curr] + 1;
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}

	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				inv[vid[i]] = i;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}

	void for_each(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		f(max(vid[head[v]], vid[u]), vid[v]);
		if (head[u] != head[v]) for_each(u, parent[head[v]], f);
	}

	void for_each_directed(int u, int v, function<void(int, int, int)> f) {
		if (vid[u] > vid[v]) {
			f(max(vid[head[u]], vid[v]), vid[u], 1);
			if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f);
		} else {
			f(max(vid[head[v]], vid[u]), vid[v], 0);
			if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f);
		}
	}

	void for_each_edge(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		if (head[u] != head[v]) {
			f(vid[head[v]], vid[v]);
			for_each_edge(u, parent[head[v]], f);
		} else {
			if (u != v) f(vid[u] + 1, vid[v]);
		}
	}

	int ancestor(int u, int d) {
		while (true) {
			if (depth[head[u]] > depth[u] - d) {
				d -= depth[u] - depth[head[u]] + 1;
				if (head[u] == 0) return 0;
				u = parent[head[u]];
			} else {
				return inv[vid[u] - d];
			}
		}
	}

	int lca(int u, int v) {
		if (vid[u] > vid[v]) swap(u, v);
		if (head[u] == head[v]) return u;
		return lca(u, parent[head[v]]);
	}

	int distance(int u, int v) {
		return depth[u] + depth[v] - 2 * depth[lca(u, v)];
	}
};

const int N = 1 << 19;
long long seg_sum[N * 2], seg_add[N * 2];

void init() {
  int m = n;
  n = 1;
  while (n < m) n *= 2;
}

void update(int a, int b, lint v, int k = 1, int l = 0, int r = N) {
	if (r <= a || b <= l) return;
	if (a <= l && r <= b) {
		seg_add[k] += v;
    seg_add[k] %= mod;
		seg_sum[k] += v * (r - l);
    seg_sum[k] %= mod;
		return;
	}
	update(a, b, v, k * 2 + 0, l, (l + r) / 2);
	update(a, b, v, k * 2 + 1, (l + r) / 2, r);
	seg_sum[k] = (seg_sum[k * 2 + 0] + seg_sum[k * 2 + 1] + seg_add[k] * (r - l)) % mod;
}

void add(int a, int b, lint v, int k = 1, int l = 0, int r = N) {
	if (r <= a || b <= l) return;
	if (a <= l && r <= b) {
		seg_add[k] += v;
    seg_add[k] %= mod;
		seg_sum[k] += v * (c[r] - c[l] + mod) % mod;
    seg_sum[k] %= mod;
		return;
	}
	add(a, b, v, k * 2 + 0, l, (l + r) / 2);
	add(a, b, v, k * 2 + 1, (l + r) / 2, r);
	seg_sum[k] = (seg_sum[k * 2 + 0] + seg_sum[k * 2 + 1] + (seg_add[k] % mod) * (c[r] - c[l] + mod) % mod) % mod;
}

lint sum(int a, int b, int k = 1, int l = 0, int r = N) {
	if (r <= a || b <= l) return 0;
	if (a <= l && r <= b) return seg_sum[k] %= mod;
	lint sl = sum(a, b, k * 2 + 0, l, (l + r) / 2);
	lint sr = sum(a, b, k * 2 + 1, (l + r) / 2, r);
	return (sl + sr + (seg_add[k] % mod) * (c[r] - c[l] + mod) % mod) % mod;
}

void po() {
  for (int i = 0; i < n; ++i) {
    cout << sum(i, i + 1) << " ";
  }
  puts("");
}

signed main() {
  cin >> n;

  HLDecomposition hld(n);

  rep(i, n) s.pb(in());
  rep(i, n) v.pb(in());

  rep(i, n - 1) {
    int a = in() - 1, b = in() - 1;
    hld.add(a, b);
  }

  hld.build();

  init();
  c.resize(n + 1);

  rep(i, n) {
    hld.for_each(i, i, [&](int l, int r){ update(l, r + 1, s[i]); c[l + 1] = v[i]; });
  }

  //print(c);

  rep(i, n) {
    c[i + 1] += c[i];
    c[i + 1] %= mod;
  }

  int q = in();
  rep(_, q) {
    int f = in();

    if (f) {
      lint ans = 0;
      int u = in() - 1, v = in() - 1;
      hld.for_each(u, v, [&](int l, int r) {
        ans += sum(l, r + 1);
        ans %= mod;
      });

      print(ans);
    } else {
      int u = in() - 1, v = in() - 1, z = in();
      hld.for_each(u, v, [&](int l, int r) {
        add(l, r + 1, z);
        //printf("(%d, %d] ", l, r);
      });
      //puts("");
    }

    //po();
  }
}
0