#1157029 (C++23) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: kwm_t
• 提出日時: 2026-04-11 05:08:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 987 ms / 10,000 ms
• コード長: 6,239 bytes
• コンパイル時間: 7,089 ms
• コンパイル使用メモリ: 392,644 KB
• 実行使用メモリ: 41,984 KB
• 最終ジャッジ日時: 2026-04-11 05:08:45
• 合計ジャッジ時間: 18,093 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

ファイルパターン	結果
other	AC * 3

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
//using namespace std;
using namespace atcoder;
using mint = modint1000000007;
const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP
#define KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP

#include <vector>
#include <algorithm>

/**
 * @brief Heavy-Light Decomposition（HLD, 重軽分解）のコア実装
 *
 * 木をパス・部分木クエリに適した区間に分解する。
 * データ構造（Segment Tree / Lazy Segment Tree など）は外部に持たせる設計。
 *
 * 典型用途:
 *   - LCA（Lowest Common Ancestor）
 *   - 木上のパスクエリ（和・最小値・xorなど）
 *   - パス更新（Lazy SegTreeと組み合わせ）
 *   - 部分木クエリ
 *
 * 計算量:
 *   - build: O(N)
 *   - lca / la / dist: O(log N)
 *   - for_each_path: O(log N) 回の区間分割
 *
 * @tparam
 *   特になし（グラフは vector<vector<int>> で受け取る）
 *
 * @param
 *   g: 隣接リスト形式の木（0-indexed）
 *
 * 制約 / 注意:
 *   - 木であること（連結・サイクルなし）
 *   - rootはbuild時に指定可能（デフォルト0）
 *   - 非可換演算の場合は、for_each_pathの順序に注意して自分で管理すること
 *   - 辺クエリは「子ノードに値を持たせる」ことで対応
 *
 * 使用例:
 *   HLD hld(g);
 *   hld.build();
 *
 *   // パスクエリ
 *   long long res = 0;
 *   hld.for_each_path(u, v, [&](int l, int r) {
 *       res += seg.prod(l, r);
 *   });
 *
 * verified:
 *   - AtCoder Library Practice Contest
 *   - ABC / ARC 木クエリ系問題
 */
namespace kwm_t::graph {

class HeavyLightDecomposition {
private:
	int n;
	std::vector<std::vector<int>> g;

	std::vector<int> sz, par, depth;
	std::vector<int> in, out, head, rev;

	void dfs_sz(int v, int p) {
		par[v] = p;
		sz[v] = 1;
		for (auto& to : g[v]) {
			if (to == p) continue;
			depth[to] = depth[v] + 1;
			dfs_sz(to, v);
			sz[v] += sz[to];
			if (sz[to] > sz[g[v][0]] || g[v][0] == p) {
				std::swap(to, g[v][0]);
			}
		}
	}

	void dfs_hld(int v, int p, int& t) {
		in[v] = t;
		rev[t] = v;
		++t;
		for (auto to : g[v]) {
			if (to == p) continue;
			head[to] = (to == g[v][0] ? head[v] : to);
			dfs_hld(to, v, t);
		}
		out[v] = t;
	}

public:
	HeavyLightDecomposition(const std::vector<std::vector<int>>& graph)
		: n(graph.size()), g(graph),
		sz(n), par(n), depth(n),
		in(n), out(n), head(n), rev(n) {}

	void build(int root = 0) {
		depth[root] = 0;
		dfs_sz(root, -1);
		int t = 0;
		head[root] = root;
		dfs_hld(root, -1, t);
	}

	// LCA
	int lca(int u, int v) const {
		while (head[u] != head[v]) {
			if (depth[head[u]] > depth[head[v]]) u = par[head[u]];
			else v = par[head[v]];
		}
		return (depth[u] < depth[v] ? u : v);
	}

	// k-th ancestor
	int la(int v, int k) const {
		while (true) {
			int h = head[v];
			if (in[v] - k >= in[h]) return rev[in[v] - k];
			k -= (in[v] - in[h] + 1);
			v = par[h];
		}
	}

	int dist(int u, int v) const {
		int w = lca(u, v);
		return depth[u] + depth[v] - 2 * depth[w];
	}

	// ===== 頂点パス =====
	// 区間 [l, r) をコールバックに渡す
	template <class F>
	void for_each_path(int u, int v, const F& f) const {
		while (head[u] != head[v]) {
			if (depth[head[u]] > depth[head[v]]) {
				f(in[head[u]], in[u] + 1);
				u = par[head[u]];
			}
			else {
				f(in[head[v]], in[v] + 1);
				v = par[head[v]];
			}
		}
		if (depth[u] > depth[v]) std::swap(u, v);
		f(in[u], in[v] + 1);
	}

	// ===== 辺パス =====
	template <class F>
	void for_each_path_edge(int u, int v, const F& f) const {
		while (head[u] != head[v]) {
			if (depth[head[u]] > depth[head[v]]) {
				f(in[head[u]], in[u] + 1);
				u = par[head[u]];
			}
			else {
				f(in[head[v]], in[v] + 1);
				v = par[head[v]];
			}
		}
		if (u == v) return;
		if (depth[u] > depth[v]) std::swap(u, v);
		f(in[u] + 1, in[v] + 1);
	}

	// ===== 部分木 =====
	template <class F>
	void for_each_subtree(int v, const F& f) const {
		f(in[v], out[v]);
	}

	// ===== getter =====
	int get_in(int v) const { return in[v]; }
	int get_out(int v) const { return out[v]; }
	int get_rev(int i) const { return rev[i]; }
	int get_par(int v) const { return par[v]; }
	int get_depth(int v) const { return depth[v]; }
};

}

#endif // KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP


struct S { mint sum, cost; };
struct F { mint x; };
S op(S sl, S sr) { return S{ sl.sum + sr.sum, sl.cost + sr.cost }; }
S e() { return S{ 0, 0 }; }
S mapping(F f, S s) { return S{ s.sum + s.cost * f.x, s.cost }; }
F composition(F f, F g) { return F{ f.x + g.x }; }
F id() { return F{ 0 }; }
int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<long long>s(n), c(n);
	rep(i, n)cin >> s[i];
	rep(i, n)cin >> c[i];
	vector<vector<int>>g(n);
	rep(i, n - 1) {
		int u, v; cin >> u >> v; u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	kwm_t::graph::HeavyLightDecomposition hld(g);
	hld.build();
	//hld.debug();
	vector<S>x(n);
	rep(i, n)x[hld.get_in(i)] = S{ s[i],c[i] };
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(x);
	int q; cin >> q;
	while (q--) {
		int t; cin >> t;
		if (0 == t) {
			int x, y, z; cin >> x >> y >> z; x--; y--;
			auto f = [&](int l, int r) {
				seg.apply(l, r, F{ z });
			};
			hld.for_each_path(x, y, f);
		}
		else {
			int x, y; cin >> x >> y; x--; y--;
			S ans = e();
			auto f = [&](int l, int r) {
				ans = op(ans, seg.prod(l, r));
			};
			hld.for_each_path(x, y, f);
			cout << ans.sum.val() << endl;
		}
	}
	return 0;
}