C++ の動作確認をしてみた（４６３）

C++の練習を兼ねて, 競プロ典型 90 問の問題039 (Tree Distance) を解いてみた.

■感想.
1. 問題039は, 方針を決めるまでに苦労したものの, ある辺が, 部分木を考えた時に, 何回カウントされるかを, 追いかけていく動的計画法で解決しそうに見えたので実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題039 をご覧下さい.

■C++版プログラム(問題039／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<LL, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
LL subTree[101010]; // 部分木の大きさ.
LL dp[101010];      // 木dp.

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    // rep(i, N) printf("%lld ", d[i]);
    // puts("");
    
    // 3. 木dp更新準備.
    // 3-1. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 3-2. 葉について, dp初期化.
    rep(i, N) if(G[i].size() == 1) dp[i] = (LL)(N - 1);
    
    // 3-3. 但し, 根は, ゼロを設定.
    dp[0] = 0;
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 部分木更新.
        subTree[v]++;
        
        // 4-4. 頂点 v を 根とする部分木 の サイズ を 集計しながら, 木dp も 更新.
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 1 から, より遠いものを加算.
                subTree[v] += subTree[u];
                
                // 頂点 v の 周囲 の 頂点 u について, 木dp の 更新.
                dp[v] += dp[u];
            }
        }
        
        // 4-5. 部分木をベースに, 木dp更新.
        if(G[v].size() > 1) dp[v] += (LL)(N - subTree[v]) * subTree[v];
    }
    
    // 5. 出力.
    printf("%lld\n", dp[0]);
    return 0;
    
}

100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<LL, int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define a first

#define b second

LL subTree[101010]; // 部分木の大きさ.

LL dp[101010]; // 木dp.

int main(){

// 1. 入力情報.

int N, a, b;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 頂点 1 から各頂点までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

// 2-4. 取り出した要素を処理.

for(auto &e : G[u]){

// 2-5. 未訪問の頂点を処理.

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, 0, d);

// rep(i, N) printf("%lld ", d[i]);

// puts("");

// 3. 木dp更新準備.

// 3-1. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}

// 3-2. 葉について, dp初期化.

rep(i, N) if(G[i].size() == 1) dp[i] = (LL)(N - 1);

// 3-3. 但し, 根は, ゼロを設定.

dp[0] = 0;

// 4. 木dp.

while(!pq.empty()){

// 4-1. 頂点 v を一つ取り出す.

P p = pq.top();

pq.pop();

// 4-2. 頂点 v の頂点番号は？

int v = p.b;

// 4-3. 部分木更新.

subTree[v]++;

// 4-4. 頂点 v を根とする部分木のサイズを集計しながら, 木dp も更新.

for(auto &u : G[v]){

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u で, 頂点 1 から, より遠いものを加算.

subTree[v] += subTree[u];

// 頂点 v の周囲の頂点 u について, 木dp の更新.

dp[v] += dp[u];

}

// 4-5. 部分木をベースに, 木dp更新.

if(G[v].size() > 1) dp[v] += (LL)(N - subTree[v]) * subTree[v];

}

// 5. 出力.

printf("%lld\n", dp[0]);

return 0;

}

[入力例]
2
1 2

[出力例]
1
※AtCoderテストケースより

[入力例]
4
1 2
1 3
1 4

[出力例]
9
※AtCoderテストケースより

[入力例]
12
1 2
3 1
4 2
2 5
3 6
3 7
8 4
4 9
10 5
11 7
7 12

[出力例]
211
※AtCoderテストケースより

[入力例]
9
1 2
5 1
3 2
2 4
5 6
6 7
8 6
6 9

[出力例]
98

[入力例]
12
1 2
2 3
3 4
3 5
2 6
1 12
1 7
7 8
7 9
7 10
7 11

[出力例]
185

[入力例]
20
1 20
2 20
2 6
6 8
7 6
7 9
7 10
7 11
3 20
3 5
3 4
4 13
4 12
4 14
14 17
14 16
14 15
18 20
18 19

[出力例]
757

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

1 2

3 1

4 2

2 5

3 6

3 7

8 4

4 9

10 5

11 7

7 12

[出力例]

211

※AtCoderテストケースより

[入力例]

1 2

5 1

3 2

2 4

5 6

6 7

8 6

6 9

[出力例]

[入力例]

1 2

2 3

3 4

3 5

2 6

1 12

1 7

7 8

7 9

7 10

7 11

[出力例]

185

[入力例]

1 20

2 20

2 6

6 8

7 6

7 9

7 10

7 11

3 20

3 5

3 4

4 13

4 12

4 14

14 17

14 16

14 15

18 20

18 19

[出力例]

757

■参照サイト
039 – Tree Distance

C++の練習を兼ねて, 競プロ典型 90 問 の 問題039 (Tree Distance) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, 競プロ典型 90 問の問題039 (Tree Distance) を解いてみた.

コメントを残すコメントをキャンセル