方法簡述:

輸入所有的邊，並建立父子關係

dfs，碰到葉子節點就把前面的東西加到他的祖先清單裡，並把葉節點加進一個大清單

如果根結點只有一個子節點，就把根結點也加入大清單

遍歷大清單，找出他們之間的距離(距離公式為節點深度的總和-最深的共同祖先的深度*2)並輸出最大值

請問要怎麼優化

package apcs;

import java.util.*;

public class b697 {

public static void dpf(Stack<node>allgrand,List<node>leaf,int deep,node head) {

allgrand.add(head);

for(node e:head.child) {

e.deep=deep+1;

dpf(allgrand,leaf,deep+1,e);

}

allgrand.pop();

if(head.child.isEmpty()) {

head.grand=new ArrayList<>(allgrand);

leaf.add(head);

}

}

public static void main(String []args) {

Scanner sc=new Scanner(System.in);

while(sc.hasNextLine()) {

List<node>leaf=new ArrayList<>();

int t=sc.nextInt();

sc.nextLine();

node[]fam=new node[t];

for(int i=0;i<t;i++)

fam[i]=new node(i);

for(int i=0;i<t-1;i++) {

String[]s=sc.nextLine().split(" ");

int a=Integer.parseInt(s[0]);

int b=Integer.parseInt(s[1]);

fam[b].father=fam[a];

fam[a].child.add(fam[b]);

}

node head=fam[0];

while(head.father!=null) {

head=head.father;

}

head.grand.add(head);

dpf(new Stack<node>(),leaf,0,head);//計算深度和直系祖先

if(head.child.size()==1)

leaf.add(head);

int far=0;

for(int i=0;i<leaf.size()-1;i++)

for(int j=i+1;j<leaf.size();j++) {

node e=leaf.get(i);

node f=leaf.get(j);

node young=e.deep>f.deep?e:f;

node old=e.deep>f.deep?f:e;

old.grand.retainAll(young.grand);

int max=old.grand.get(old.grand.size()-1).deep;

far=Math.max(far,e.deep+f.deep-max*2);

}

System.out.println(far);

}

sc.close();

}

}

class node {

int data;

node father;

int deep;

List<node>grand=new ArrayList<>();

List<node>child=new ArrayList<>();

public node(int data) {

this.data=data;

}

}