【競プロ】1日1AC : ABC138 D問題 Ki

今日の問題はこれです。

Diffは923(緑)。
前回の記事でまとめた、木構造が出てくる問題です。問題文の意味が分からない人はこの記事を読みましょう。

【競プロ】木構造について初心者向けにまとめる

2020年4月21日

ちょっと難しいところもありますが、少し考えてみてください。

提出コードと考え方

ちょっと具体例を書きましょう。

入力例1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

上の画像のように、各部分木に値を足していきます。各頂点のカウンターの値は、操作の順番によらないことがわかるでしょう。

問題になるのはカウンターに値を加える部分です。問題文の通りに操作をシミュレーションすると、例えば頂点 \(1\) に \(Q\) 回の操作をする場合は \(\mathcal{O}(NQ)\) となるため間に合いません。

ちょっと工夫をしましょう。

ある頂点を根とする部分部分木全体に値を足すのではなく、子に値を足すことを繰り返しましょう。つまり、頂点 \(1\) を根とする部分木に操作を行うときは、

  1. 頂点 \(1\) に \(+100\)
  2. 頂点 \(1\) の子である頂点 \(2\) に \(+100\)
  3. 頂点 \(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を理解しよう

2020年4月12日

あと説明すべきは最後の出力でしょうか。三項演算子を用いています。

(条件式) ? (条件式が真の時の値) : (条件式が偽の時の値)

こうすることで、「最後だけ改行、他はスペース区切り」とすることができます。(最後も空白にしてもジャッジは通りますが。)

終わりに

予想以上に長い記事になって疲れました。BFSでの実装は元気があれば追記します。

コメント