大神的世界

想法 : AOV (active on vertex)

每個 node 要紀錄三件事

(1) parent

(2) indegree

(3)最遠、次遠 ( 到葉子的距離)

因此中間節點產生的最遠"血緣距離" 就是最遠 + 次遠

而我們要找的就是這些值的最大值

至於這最遠、次遠要怎麼找呢?

我們採用 bottom-up 的方式

leaves 的最遠次遠是 0,0 對吧

把 leaves 的資訊丟給 parent，但我們只丟最遠，代表的是 parent 往 leaf 這方向最遠 node 的距離有多遠

但別忘了要加 1 ，因為 leaf 到 parent 差了一步

當該 parent 接收完所有 leaves 的資訊後，它就有最遠和次遠資訊，接著將該 parent 視作 leaf 繼續往上更新

最後結果如下

我們得知，最遠"血緣距離" 為 4 ( node 0 => 2 + 2 )

下面提供原版和解答，我比較喜歡原版，但會 TLE (原版比較看得懂)

解答

#include <iostream>
#include <queue>

constexpr int MAX_NODE_NUM = 100000;

using namespace std;

struct Node
{
    int m_parent;
    int m_indegree;
    int m_max_distance[2];
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    Node node[MAX_NODE_NUM];

    int node_num;
    while(cin >> node_num){
        for(int i = 0; i<node_num; i+=1){
            node[i] = {-1, 0, {}};
        }

        for(int i = 0; i<node_num-1; i+=1){
            int parent, child;
            cin >> parent >> child;

            node[child].m_parent = parent;;
            node[parent].m_indegree += 1;
        }

        queue<int> leave;
        for(int i = 0 ;i<node_num; i+=1)
            if(node[i].m_indegree == 0)
                leave.push(i);

        int max_distance = 0;
        while(!leave.empty()){
            int leaf = leave.front(); leave.pop();
            int parent = node[leaf].m_parent;

            if(parent == -1) continue;  //root

            int value = node[leaf].m_max_distance[0] + 1;
            if(value > node[parent].m_max_distance[0]){
                node[parent].m_max_distance[1] = node[parent].m_max_distance[0];
                node[parent].m_max_distance[0] = value;
            }
            else if(value > node[parent].m_max_distance[1])
                node[parent].m_max_distance[1] = value;

            node[parent].m_indegree -= 1;
            if(node[parent].m_indegree == 0)
                leave.push(parent);

            int distance = node[parent].m_max_distance[0] + node[parent].m_max_distance[1];
            if(distance > max_distance)
                max_distance = distance;
        }

        cout << max_distance << endl;
    }

    return 0;
}

原版

#include <iostream>
#include <queue>

constexpr int MAX_NODE_NUM = 100000;

using namespace std;

class Node
{
public:
    void init()
    {
        m_parent = -1;
        m_indegree = 0;
        m_max_distance[0] = m_max_distance[1] = 0;
    }

    int getParent() const{ return m_parent; }
    int getIndegree() const { return m_indegree; }
    int getMaxDistance() const { return m_max_distance[0] + 1; }
    int getMaxDistanceSum() const { return m_max_distance[0] + m_max_distance[1]; }
    void setParent(const int &_num) { m_parent = _num; }
    void addIndegree(const int &_num) { m_indegree += _num; }
    void updateMaxDistance(const int &_num)
    {
        if(_num > m_max_distance[0]){
            m_max_distance[1] = m_max_distance[0];
            m_max_distance[0] = _num;
        }
        else if(_num > m_max_distance[1])
            m_max_distance[1] = _num;
    }

private:
    int m_parent;
    int m_indegree;
    int m_max_distance[2];
};

int main()
{
    Node node[MAX_NODE_NUM];

    int node_num;
    while(cin >> node_num){
        for(int i = 0; i<node_num; i+=1)
            node[i].init();

        for(int i = 0; i<node_num-1; i+=1){
            int parent, child;
            cin >> parent >> child;

            node[child].setParent(parent);
            node[parent].addIndegree(1);
        }

        queue<int> leave;
        for(int i = 0 ;i<node_num; i+=1)
            if(node[i].getIndegree() == 0)
                leave.push(i);

        int max_distance = 0;
        while(!leave.empty()){
            int leaf = leave.front(); leave.pop();
            int parent = node[leaf].getParent();

            if(parent == -1) continue;  //root

            node[parent].updateMaxDistance(node[leaf].getMaxDistance());
            node[parent].addIndegree(-1);
            if(node[parent].getIndegree() == 0)
                leave.push(parent);

            if(node[parent].getMaxDistanceSum() > max_distance)
                max_distance = node[parent].getMaxDistanceSum();
        }

        cout << max_distance << endl;
    }

    return 0;
}