#35241: 好難


jasperlin0108@gmail.com (Jasper Lin)

學校 : 高雄市立高雄高級中學
編號 : 169403
來源 : [114.40.142.198]
最後登入時間 :
2023-10-05 16:52:06
b967. 4. 血緣關係 -- 2016年3月apcs | From: [101.9.37.209] | 發表日期 : 2023-05-18 15:30

因為英文不好,所以變數名稱很奇怪。

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    vector<Node*> child;
    Node* dad=nullptr;
    int floor=0;
};

int find_floor(Node* n)
{
    if(!n->child.empty())
    {
        for(int i=0; i<n->child.size(); i++)
        {
            n->floor=max(n->floor,find_floor(n->child[i])+1);
        }
    }
    return n->floor;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while( cin>>n)
    {
        vector<Node*> tree;
        for(int i=0; i<n; i++)
        {
            Node* ne=new Node;
            tree.push_back(ne);
        }
        int a,b;
        for(int i=0; i<n-1; i++)
        {
            cin>>a>>b;
            tree[b]->dad=tree[a];
            tree[a]->child.push_back(tree[b]);
        }
        Node* root=tree[0];
        while(root->dad!=nullptr)
        {
            root=root->dad;
        }
        find_floor(root);
        int case_1=0,case_2=0;
        case_1=root->floor;
        for(int i=0; i<n; i++)
        {
            if(tree[i]->child.size()>=2)
            {
                if(tree[i]->child.size()>2)
                {
                    for(int j=0; j<2; j++)
                    {
                        for(int k=j+1; k<tree[i]->child.size(); k++)
                        {
                            if(tree[i]->child[j]->floor<tree[i]->child[k]->floor)
                            {
                                Node* tmp=tree[i]->child[k];
                                tree[i]->child[k]=tree[i]->child[j];
                                tree[i]->child[j]=tmp;
                            }
                        }
                    }
                }
                case_2=max(case_2,tree[i]->child[0]->floor+tree[i]->child[1]->floor+2);
            }
        }
        cout<<max(case_1,case_2)<<"\n";
    }

 


    return 0;
}

 
ZeroJudge Forum