今日の問題はこれです。
Diffは923（緑）。
前回の記事でまとめた、木構造が出てくる問題です。問題文の意味が分からない人はこの記事を読みましょう。
ちょっと難しいところもありますが、少し考えてみてください。
提出コードと考え方
ちょっと具体例を書きましょう。
4 3
1 2
2 3
2 4
2 10
1 100
3 1
上の画像のように、各部分木に値を足していきます。各頂点のカウンターの値は、操作の順番によらないことがわかるでしょう。
問題になるのはカウンターに値を加える部分です。問題文の通りに操作をシミュレーションすると、例えば頂点 \(1\) に \(Q\) 回の操作をする場合は \(\mathcal{O}(NQ)\) となるため間に合いません。
ちょっと工夫をしましょう。
ある頂点を根とする部分部分木全体に値を足すのではなく、子に値を足すことを繰り返しましょう。つまり、頂点 \(1\) を根とする部分木に操作を行うときは、
- 頂点 \(1\) に \(+100\)
- 頂点 \(1\) の子である頂点 \(2\) に \(+100\)
- 頂点 \(2\) の子である頂点 \(3,4\) に \(+100\)
とすることができるでしょう。
さらに、この操作は \(Q\) 回に分けて行う必要がないことがわかります。
「頂点 \(p_i\) を根とする部分木に含まれる頂点のカウンターに \(x_i\) を加える」という操作の代わりに、「頂点 \(p_i\) のみに \(x_i\) を加える」とします。
図の例では、カウンターの初期値は頂点 \(1\) から順に「\(100,10,1,0\)」です。
頂点 \(1\) から順に「自分の子に自分のカウンターの値を足す」という操作を行えば、\(\mathcal{O}(N)\) でこの問題を解くことができます。
全ての頂点を辿る必要があるので、BFSかDFSを使いましょう。実装はDFSの方が楽なので、提出コードはそっちで書いています。
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
int MX = 200000;
vector<vector<int>> G(MX,vector<int>());
vector<int> ans(MX);
void dfs(int i,int p = -1){
for(auto v : G[i]){
// pは親、iは今見ている頂点、vは子
if(v == p) continue;
ans[v] += ans[i];
dfs(v,i);
}
return;
}
int main(){
int n,q;
cin >> n >> q;
rep(i,n-1){
int a,b;
cin >> a >> b;
a--; b--;
G[a].push_back(b);
G[b].push_back(a);
}
rep(i,q){
int p,x;
cin >> p >> x;
p--;
ans[p] += x;
}
dfs(0);
rep(i,n) printf("%d%c",ans[i],(i == n-1) ? '\n' : ' ');
}再帰関数を用いてDFSをしています。これについては今は特に説明しませんが、再帰関数の処理を追ってもらえればなんとなくわかると思います。
BFSについては既にまとめてあるので、DFSできないよ、という人は以下の記事を参考にコードを書いてみてください。（BFSはどの問題もほぼ同じようなコードで書けますが、ちょっと長い。）
あと説明すべきは最後の出力でしょうか。三項演算子を用いています。
(条件式) ? (条件式が真の時の値) : (条件式が偽の時の値)こうすることで、「最後だけ改行、他はスペース区切り」とすることができます。（最後も空白にしてもジャッジは通りますが。）
終わりに
予想以上に長い記事になって疲れました。BFSでの実装は元気があれば追記します。
コメント