#include<iostream>
#include<vector>
#define noParent 999
using namespace std;
struct Node
{
int parent;//记录父节点编号
int layer;//记录所在层,方便求高度和宽度
}node[105];
bool process(int u, int v);
int special[205];//如果当前无法判断u, v谁是父节点或子节点,则记录u, v
int index_special = 0;
int height = 0;
int main()
{
int i;
for(i = 0; i <= 104; i++) node[i].parent = noParent;
int n;
cin >> n;//n个结点
node[1].parent = -1;
node[1].layer = 1;
for(i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
if(process(u, v))//接下来尝试处理special结点
{
vector<int> new_special;
for(int j = 0; j < index_special; j += 2)
{
if(!process(special[j], special[j + 1]))
{
new_special.push_back(special[j]);
new_special.push_back(special[j + 1]);
}
}
index_special = 0;
while(!new_special.empty())
{
special[index_special] = new_special.back();
new_special.pop_back();
index_special++;
}
}
}
int wide = 0;
int temp_wide[105];
for(i = 0; i <= 104; i++) temp_wide[i] = 0;
for(i = 1; i <= n; i++)
temp_wide[node[i].layer]++;
for(i = 1; i <= n; i++)
if(temp_wide[i] > wide) wide = temp_wide[i];
int node1, node2;
cin >> node1 >> node2;
//原理:记录node1经过的祖先结点,与node2经过的祖先结点一一比较,找到最早相同的祖先结点
int len1 = 0, len2 = 0;
int para1[105];
int para1_index = 0;
//必须保存node1自己信息,因为可能node1就是node2父节点
para1[para1_index] = node1;
para1_index++;
while(node[node1].parent != -1)
{
node1 = node[node1].parent;
para1[para1_index] = node1;
para1_index++;
}
while(1)
{
int flag = 0;
for(i = 0; i < para1_index; i++)
{
if(node2 == para1[i])
{
len1 = i;
flag = 1;
break;
}
}
if(flag == 1) break;
len2++;
node2 = node[node2].parent;
}
cout << height << endl << wide << endl << len1 * 2 + len2;
}
//测试距离 10 7,10 3,8 7均正确
bool process(int u, int v)
{
int child, paren;
int temp_index;
//判断u,v谁是父节点,谁是子节点
if(node[u].parent == noParent && node[v].parent != noParent)
{
child = u;
paren = v;
}
else if(node[v].parent == noParent && node[u].parent != noParent)
{
child = v;
paren = u;
}
else//目前都没父节点
{
special[index_special] = u;
index_special++;
special[index_special] = v;
index_special++;
return false;
}
node[child].parent = paren;
node[child].layer = node[paren].layer + 1;
if(node[child].layer > height) height = node[child].layer;
return true;
}
求大佬解答,谢谢!!!