#38035: bottom-up解法(注意每個節點要存最大兩高度


100200 (Yu Xuan)

學校 : 高雄市立高雄高級中學
編號 : 169890
來源 : [101.8.39.61]
最後登入時間 :
2024-05-08 18:03:53
b967. 4. 血緣關係 -- 2016年3月apcs | From: [58.115.145.189] | 發表日期 : 2023-10-22 23:50

#include <bits/stdc++.h>
using namespace std;
struct Max
{
    int m1, m2;
};
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int parent[n];
        int deg[n] = {0};
        queue<int> Q;
        Max max_2h[n] = {0, 0};
        for (int i = 0; i < n; i++) parent[i] = -1;
        for (int i = 1; i < n; i++)
        {
            int p, c;
            scanf("%d %d", &p, &c);
            parent[c] = p;
            deg[p] += 1;
        }
        for (int i = 0; i < n; i++) if (deg[i] == 0) Q.push(i);
        int ans = 0;
        while(!Q.empty())
        {
            int point = Q.front();
            Q.pop();
            if (parent[point] == -1) continue;
            int Parent = parent[point];
            max_2h[Parent].m1 = max(max_2h[Parent].m1, max_2h[point].m2+1);
            if (max_2h[Parent].m1 > max_2h[Parent].m2) swap(max_2h[Parent].m1, max_2h[Parent].m2);
            ans = max(ans, max_2h[Parent].m1+max_2h[Parent].m2);

            if ((--deg[Parent]) == 0) Q.push(Parent);

        }
        printf("%d\n", ans);

    }
}

 
ZeroJudge Forum