NF

地方で働くプログラマ

zennzenn wakarann（AOJ Course GRL_5_A）

Linux

木構造とかDFSとか。
取り合えず典型とか言われてる問題をやってるけど全然わからん。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A&lang=ja


入力例１だとこんな木ですかね。上下の数字が距離です。パッと見で0->1->3が最大ですね。

　　 2　　　1
[0] ━━ [1] ━━ [2]
　　　　┗━━ [3]
　　　　　3


取り合えず木を走査する部分はできた。距離の計算どうすればいいんだ。Webで出てくる解説には2回DFSをすると書いてあるけど何でそうなるのか全然理解できない。。もうプログラムの仕事辞めたくなるな。いやプログラムなんて最近ほとんど書けないけど。

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

struct Edge
{
    int to;
    int cost;
};
std::vector<Edge> v[100009];

void dfs(const int index, const int parent_index)
{
    printf("\n頂点%dを調べる（親は頂点%d、接点数は%lu）\n",
           index, parent_index, v[index].size());
    std::vector<Edge>::iterator itr;
    for(itr = v[index].begin(); itr != v[index].end(); ++itr){
        int to = itr->to;
        int cost = itr->cost;
        if(to == parent_index){
            printf("  -> 頂点%d は親なので飛ばす\n", to);
            continue;
        }
        printf("  -> 頂点%dと頂点%dとの距離は%d\n", index, to, cost);
        dfs(to, index);
    }
    printf("頂点%dの調査終わり\n\n", index);
}
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n-1; i++){  // 辺の数は(頂点の数-1)
        int s,t,w;
        cin >> s >> t >> w;
        Edge e;
        e.cost = w;
        e.to = t; v[s].push_back(e);
        e.to = s; v[t].push_back(e);
    }
    for(int i=0; i<n; i++){
        printf("頂点%dからは ", i);
        std::vector<Edge>::iterator itr = v[i].begin();
        while(itr != v[i].end()){
            printf("%d(長さ%d), ", itr->to, itr->cost);
            ++itr;
        }
        printf("に接している\n");
    }
    printf("\n");

    dfs(0, -1);
    return 0;
}


入力例 １の実行結果

頂点0からは 1(長さ2), に接している
頂点1からは 0(長さ2), 2(長さ1), 3(長さ3), に接している
頂点2からは 1(長さ1), に接している
頂点3からは 1(長さ3), に接している


頂点0を調べる（親は頂点-1、接点数は1）
  -> 頂点0と頂点1との距離は2

頂点1を調べる（親は頂点0、接点数は3）
  -> 頂点0 は親なので飛ばす
  -> 頂点1と頂点2との距離は1

頂点2を調べる（親は頂点1、接点数は1）
  -> 頂点1 は親なので飛ばす
頂点2の調査終わり

  -> 頂点1と頂点3との距離は3

頂点3を調べる（親は頂点1、接点数は1）
  -> 頂点1 は親なので飛ばす
頂点3の調査終わり

頂点1の調査終わり

頂点0の調査終わり


一日掛けて全然理解が進まなくて正直辛くなってきた。初心者のまま誰にも聞けない環境は無理だと感じてたけどほんとうにキツい。一旦寝てもう少しだけ続ける…

取り合えず読んでるサイトメモ
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita
木構造のDFS（AtCoder Beginner Contest 138より） - Qiita

もし理解できたら次に解きたかった問題
D - Ki
K - 木の問題
C - 木の問題
B - Counting of Trees


それとこの辺
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=GRL


（2020/3/22追記）
なんとかACしました。
提出コード（ID出るのでやめました）


方針は、こちらのサイトを参考にして、恐らくスタンダードな木の直径を求めるやり方：①適当な始点から深さ優先探索で最大距離を求めて、②その最大距離の頂点から再度深さ優先探索で最大距離を求める、でやりました（実装はあまり真似できなかった）。一応、けんちょんさんの記事とかにあるように他の解き方もあるようです。（こっちの解法は初級者向けではなさそう）

なんで深さ優先探索（DFS）を2回やるかというと、下のような木の場合は最大距離は0->1->3じゃなくて3->1->2になるからですね。最初ここが分からなかったです。

　　 2　　　3
[0] ━━ [1] ━━ [2]
　　　　┗━━ [3]
　　　　　3

最大距離は、色々やり方があるようですが、DFSの引数に最大距離を追加して、枝を通ったら足しこむようにしました。終点（葉）は始点じゃない且つ親としか枝が繋がってない、で判断できるので、このタイミングで現在の最大距離と比較して大きければ更新するようにしました。

以下、コメントとかを消したコードです。

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

// 頂点情報を格納するベクタ
struct Edge
{
    int to;
    int cost;
};
std::vector<Edge> v[100009];

// firstが始点から最大距離の頂点、secondが最大距離
std::pair<int, int> max_cost;

void dfs(const int index, const int parent_index, const int total_cost)
{
    if(v[index].size() == 1 && parent_index != -1){
        // 接点が親だけの場合は葉なので最大距離を更新する
        if(total_cost > max_cost.second){
            max_cost.first = index;
            max_cost.second = total_cost;
        }
    }
    std::vector<Edge>::iterator itr;
    for(itr = v[index].begin(); itr != v[index].end(); ++itr){
        int to = itr->to;
        int cost = itr->cost;
        if(to == parent_index) continue;
        dfs(to, index, total_cost+cost);
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n-1; i++){  // 辺の数は(頂点の数-1)
        int s,t,w;
        cin >> s >> t >> w;
        Edge e;
        e.cost = w;
        e.to = t; v[s].push_back(e);
        e.to = s; v[t].push_back(e);
    }
    for(int i=0; i<n; i++){
        std::vector<Edge>::iterator itr = v[i].begin();
        while(itr != v[i].end()){
            ++itr;
        }
    }

    dfs(0, -1, 0);
    dfs(max_cost.first, -1, 0);
    printf("%d\n", max_cost.second);
    
    return 0;
}

いや、ちょっとすっきしました。昼飯食べてくるか…

あぁあと、初学者（茶色中盤くらい）はAOJを見るべきというのが分かりました。この辺、意外と初心者困惑すると思うんですよね、実際掲示板とかで自分と同じように困ってて質問してる人も観測しました。灰色→茶色（前半）になるための情報は色々ある（こことか）んですが、茶色（前半）→茶色（後半）くらいの人がどうすればいいか、っていう情報（というか学習ルート）って意外と充実してないと感じる。