# 資料結構題 - 樹狀圖分析 - APCS - by Peter Wang
## 題目資訊
此題為2017.10.18 測驗中的題目3
###### tags: `APCS` `Tree` `DFS`

## Rooted Tree定義

在一棵 *n* 個節點的有根樹中,每個節點都是以 *1~n* 的不同數字來編號,描述一棵有根樹必須定義節點與節點之間的親子關係。一棵有根樹恰有一個節點沒有父節點(parent),此節點被稱為根節點(root),除了根節點以外的每一個節點都恰有一個父節點,而每個節點被稱為是它父節點的子節點(child),有些節點沒有子節點,這些節點稱為葉節點(leaf)。在當有根樹只有一個節點時,這個節點既是根節點同時也是葉節點。在圖形表示上,我們將父節點畫在子節點之上,中間畫一條邊(edge)連結。例如：下圖中表示的是一棵 9 個節點的有根樹,其中,節點 1 為節點 6 的父節點,而節點 6 為點 1 的子節點;又 5 、 3 與 8 都是 2 的子節點。節點 4 有父節點,所以節點 4 是根節點;而 6 、 9 、 3 與 8 都是葉節點。
## DFS概述
如下圖由 4 開始走訪按照數字順序依序 DFS ，這也是基本 DFS 圖像化的概念。
當然 DFS 還有分成不同種走訪方式這裡就先不多做解釋。
## 題目敘述
樹狀圖中的兩個節點 *u* 和 *v* 之間的距離 *d ( u , v )* 定義為兩節點之間邊的數量。如上圖中：*d ( 7 , 5 ) = 2* ,而 *d ( 1 , 2 ) = 3*。對於樹狀圖中的節點點 *v* ,我們以 *h(v)* 代表節點 *v* 的高度,其定義是節點 *v* 和節點 *v* 下面最遠的葉節點之間的距離,而葉節點的高度定義為 *0* 。如上圖中,節點 6 的高度為 0 ,節點 2 的高度為 2 ,而節點 4 的高度為 4 。此外,我們定義 *H(T)* 為 *T* 中所有節點的高度總和。給定一個樹狀圖T,請找出 *T* 的根節點以及高度總和 *H(T)* 。

### 輸入：
第一行有一個正整數 n 代表樹狀圖的節點個數，節點的編號為 1 到 n 。
接下來有 n 行，第 i 行的第一個數字 k 代表節點 i 有 k 個子節點，第 i 行接下來的 k 個數字就是這些子節點的編號。

### 輸出：
輸出兩行各含一個整數，第一行是根節點的編號，第二行是 *H(T)*。

## 解題思路
利用 DFS 的技巧，在走訪過程中紀錄 i 節點走過的最大距離，並在迴圈中把所有節點之最大距離加總，同時，也比較所有節點中擁有最大距離的節點，也就是跟節點，最後輸出。

## 程式碼

#include <iostream>
#include <vector>
using namespace std;
#define ll long long 
vector <ll> tree[100004];
ll h[100004];
ll dfs(ll node){
  if(tree[node].size()==0){
    h[node]=0;
    return 0;
  }
  if(h[node]!=0){
    return h[node];
  }
  ll ch=tree[node].size();
  for(ll i=0;i<ch;i++){
    h[node]=max(h[node],dfs(tree[node][i])+1);
  }
  return h[node];
}
int main(){
  ll n;
  while(cin>>n){
    fill(h,h+n+1,0);
    for(ll i=1;i<=n;i++){
      tree[i].clear();
      ll num;
      cin>>num;
      if(num!=0){
        for(ll j=1;j<=num;j++){
          ll nn;
          cin>>nn;
          tree[i].push_back(nn);
        }
      }
    }
    ll ans=0;
    ll Node=1;
    for(ll i=1;i<=n;i++){
      ll df=dfs(i);
      ans+=df;
      if(df>h[Node]){
        Node=i;
      }
    }
    cout<<Node<<endl;
    cout<<ans<<endl;
  }
}

## 資料來源
[Zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=c463)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:59 AM]