C++の練習を兼ねて, AtCoder Beginner Contest 138 の 問題D (D – Ki) を解いてみた.
■感想.
1. 深さ優先探索時に, dp更新を行えば良いことに気付いたので, AC版に到達出来た.
2. 深さ優先探索の実装は, AtCoder Beginner Contest 070 (問題D Transit Tree Path) の 解説をベースに実装している.
本家のサイトABC 138解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAX = 210012; vector<vector<int>> graph(MAX); LL dp[MAX]; // グラフの経路を探索する. // https://ja.wikipedia.org/wiki/深さ優先探索 // @param c: 探索地点となる頂点. // @param b: 探索地点から見て, 前回探索済の頂点. // @return : 特に無し. void dfs(int c, int b){ dp[c] += dp[b]; for(int e : graph[c]){ if(e == b) continue; dfs(e, c); } } int main(){ // 1. 入力情報取得. int N, Q; scanf("%d %d", &N, &Q); for(int i = 0; i < N - 1; i++){ int a, b; scanf("%d %d", &a, &b); graph[a].push_back(b); graph[b].push_back(a); } for(int i = 0; i < Q; i++){ int p; LL x; scanf("%d %lld", &p, &x); dp[p] += x; } // 2. dp更新. dfs(1, 0); // 3. 出力 ～ 後処理. for(int i = 1; i <= N; i++) printf("%lld ", dp[i]); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
[入力例] 4 3 1 2 2 3 2 4 2 10 1 100 3 1 [出力例] 100 110 111 110 ※AtCoderテストケースより [入力例] 6 2 1 2 1 3 2 4 3 6 2 5 1 10 1 10 [出力例] 20 20 20 20 20 20 ※AtCoderテストケースより [入力例] 8 5 1 2 3 1 1 4 7 5 5 1 5 6 8 6 2 1 4 2 1 3 5 4 6 5 [出力例] 3 4 3 5 7 12 7 12 |
■参照サイト
AtCoder Beginner Contest 138