Educational Codeforces Round 54 E. Vasya and a Tree
問題
問題概要
Tree(重み付きではない)が与えられ、木の各頂点に数字を書き込む。最初は0.
以下のM
個のクエリも与えられる。
v
, d
, x
: 頂点v
と、その部分木のうち、v
からの距離がd
以内に含まれる頂点にx
を足す。
昔似た方針で解いた記憶がある。リアルタイムimosって感じ。
DFSで頂点を見ていく。DFSでは、一個前の頂点で書き込んだ数字を引数として持っておく(s
とする)。
見た頂点から、d
,x
なクエリが発行されていたら、s
にx
を一通り足す。
同時に、木の最大の深さ分の配列を用意しておいて、今見ている頂点の深さに、d
を足した先にx
を足してメモしておく。
式で表現すると、今見ている頂点の深さをdepth
とすると
memo[depth+d] += x
みたいな感じ。x
を一通り足したら、memoでメモされている分を引く。(そのクエリの範囲外に到達するため)
また、今見ている頂点が見終わったら、memoに足した分は無効化されるので、最後に引いて終了しないといけない。(ソースコード参照)
vector<vector<int> > G; vector<vector<pii> > dist_value; vector<int> res; vector<int> imos; vector<bool> is_visited; void DFS(int node, int depth, int sum){ if (is_visited[node]) return; is_visited[node] = true; for (auto &dx : dist_value[node]) { int d, x; tie(d, x) = dx; int right = min(size_t(depth + d + 1), G.size()); imos[right] -= x; sum += x; } sum += imos[depth]; res[node] = sum; for (auto &dst : G[node]) { DFS(dst, depth + 1, sum); } for (auto &dx : dist_value[node]) { int d, x; tie(d, x) = dx; int right = min(size_t(depth + d + 1), G.size()); imos[right] += x; } } void solve() { int N; cin >> N; G.resize(N); dist_value.resize(N); res.resize(N); imos.resize(N+1); is_visited.resize(N); REP(i, N-1) { int x, y; cin >> x >> y; --x, --y; G[x].push_back(y); G[y].push_back(x); } int M; cin >> M; REP(i, M) { int v, d, x; cin >> v >> d >> x; --v; dist_value[v].emplace_back(d,x); } DFS(0, 0, 0); REP(i, res.size()) { cout << res[i] << (res.size() == i + 1 ? '\n' : ' '); } }