#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int total_member;
while(scanf("%d",&total_member)!= EOF){
vector<int> family_mems; // index => the member, content => his parent;
for(int i = 0; i<total_member ; i++){
family_mems.push_back(-1); //-1 => no parent
}

for(int i = 0; i<total_member-1; i++){
int index;
int parent;
scanf("%d %d",&parent,&index);
family_mems[index] = parent;
}

//-----------get root-------------//
int root = 0;
int parent = family_mems[0];
while(parent != -1){
root = parent;
parent = family_mems[parent];
}
////////////////////////////////////

//--------Distance To Root---------//
vector <int> distance_to_root; // index => the member, content => distance to root;
for(int i = 0; i<total_member;i++){
int distance = 0;
int parent = family_mems[i];
while(parent != -1){
distance++;
parent = family_mems[parent];
}
distance_to_root.push_back(distance);
}
/////////////////////////////////////
int max_distance = 0;

for(int i = 0; i<total_member; i++){
for(int j=i+1; j<total_member; j++){
int distance = 0;
int i_base = i;
int j_base = j;

while(distance_to_root[i_base] != distance_to_root[j_base]){
if(distance_to_root[i_base] > distance_to_root[j_base]){
distance++;
i_base = family_mems[i_base];
}else{
distance++;
j_base = family_mems[j_base];
}
}

if(i_base != j_base){
int i_parent = family_mems[i_base];
int j_parent = family_mems[j_base];
while(i_parent != j_parent){
distance = distance+2;
i_parent = family_mems[i_parent];
j_parent = family_mems[j_parent];
}
distance = distance +2;
}
max_distance = max(max_distance,distance);
}
}
cout << max_distance << endl;
}
return 0;
}

最後一段求最大距離跟前面求到根的距離的部分複雜度都是O(N^2)

這題的N最高會到1e5 所以會炸

你可以試試看從根DFS一遍 複雜度只有O(N)