結果
| 問題 | No.2676 A Tourist |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-04-11 04:57:30 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,504 bytes |
| 記録 | |
| コンパイル時間 | 8,012 ms |
| コンパイル使用メモリ | 383,476 KB |
| 実行使用メモリ | 7,976 KB |
| 最終ジャッジ日時 | 2026-04-11 04:57:50 |
| 合計ジャッジ時間 | 10,467 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 2 |
| other | RE * 31 |
ソースコード
#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
using S = long long;
S op(S a, S b) { return a + b; }
S e() { return 0; }
void localInOut() {
#pragma warning(disable : 4996)
FILE *in = freopen("in.txt", "r", stdin);
FILE *out = freopen("out.txt", "w", stdout);
}
int main() {
using namespace std;
ios::sync_with_stdio(false);
cin.tie(nullptr);
localInOut();
int n, q; cin >> n >> q;
vector<long long>a(n + 1);
rep(i, n)cin >> a[i + 1];
vector<vector<int>>g(n + 1);
g[0].push_back(1);
g[1].push_back(0);
rep(i, n - 1) {
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
kwm_t::graph::HeavyLightDecomposition hld(g);
hld.build();
vector<long long>sa(n + 1);
rep2(i, 1, n + 1) {
int p = hld.la(i, 1);
sa[hld.get_in(p)] += a[i];
}
segtree<S, op, e>seg(sa);
while (q--) {
int t; cin >> t;
if (0 == t) {
int v, x; cin >> v >> x;
a[v] += x;
int p = hld.la(v, 1);
sa[hld.get_in(p)] += x;
seg.set(hld.get_in(p), sa[hld.get_in(p)]);
}
else {
int u, v; cin >> u >> v;
int l = hld.lca(u, v);
int p = hld.la(l, 1);
if (u == l || v == l) {
long long ans = a[p] + a[l];
auto f = [&](int l, int r) {
ans += seg.prod(l, r);
};
hld.for_each_path(u, v, f);
cout << ans << endl;
}
else {
long long ans = 0;
auto f = [&](int l, int r) {
ans += seg.prod(l, r);
};
hld.for_each_path(u, l, f);
hld.for_each_path(v, l, f);
ans -= sa[hld.get_in(l)];
ans += a[p] + a[l];
cout << ans << endl;
}
}
}
return 0;
}