種子論壇 | 高雄市資訊培育協會學員討論區

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class P4 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//輸入物件
int n,root;//n為總共有多少節點,root為根結點
Node node[];//宣告陣列
String str,raw[];//str為幾個節點輸入用,raw為輸入關係用
int res,finalMaxChildDis;
P4()throws Exception//建構子
{
while((str=br.readLine())!=null)
{
finalMaxChildDis=-1;//紀錄最遠親戚的距離
n=Integer.parseInt(str);//有n個節點
node=new Node[n];//宣告陣列長度
for(int i=0;i<n;i++)
node[i]=new Node();//建立n個物件
for(int i=0; i<n-1; i++)
{
//連續輸入2個值，表示父與子,空白擷取
raw=br.readLine().split(" ");
//raw[0]是父，因是字串所以做轉型，給p存
int p=Integer.parseInt(raw[0]);
//raw[1]是子，因是字串所以做轉型，給c存
int c=Integer.parseInt(raw[1]);
//node[c]的父為p;
node[c].parent=p;
//node[p]的子為c;
node[p].child.add(c);
}
//找根結點、以及找尋每個節點到葉節點的深度
for(int i=0;i<n;i++)
{
if(node[i].parent==-1)
//當節點的父親為-1表示此節點為父
root=i;
//從沒有小孩的節點開始往上推高度
if(node[i].child.size()==0)
{
//h為此節點到最後葉節點的深度,初始為0
int h=0;
//偵測此節點的父親為誰
int parent=node[i].parent;
//如推到最後節點為-1了表示到根結點了
while(parent!=-1)
{
h++;//深度加一
//比較看看h是否有大於目前節點已經有的深度紀錄(因有左右兩邊)
if(h>node[parent].h)
{
//更新目前節點到葉節點的深度
node[parent].h=h;
}
else
//若h<目前節點的h，表示不用更新，直接跳出迴圈
break;
//繼續往上找
parent=node[parent].parent;
}
}
}
//開始抓取節點到節點的距離
for(int i=0;i<n;i++)
{
if(node[i].child.size()>=2)
{
for(int j=0;j<node[i].child.size();j++)
{
int childH=node[node[i].child.get(j)].h;
if(childH>node[i].max)
{
node[i].sec=node[i].max;
node[i].max=childH;
}
else if(childH>node[i].sec)
node[i].sec=childH;
}
node[i].maxChildDis=node[i].max+node[i].sec+2;
//判斷是否有大於其他節點之孩子間的最深距離
if(node[i].maxChildDis>finalMaxChildDis)
//更新血緣關係的距離
finalMaxChildDis=node[i].maxChildDis;
}
}
}
}
class Node{
int parent=-1,h=0;
int maxChildDis=-1,max=-1,sec=-1;
ArrayList<Integer>child=new ArrayList<Integer>();
}
public static void main(String[] args)throws Exception {
// TODO 自動產生的方法 Stub
new P4();
}
}
/*
8
0 1
0 2
0 3
7 0
1 4
1 5
3 6
6
3 5
0 1
3 4
1 2
1 3
*/
}

複製代碼