题面
（因为是回忆版题面，说得不清不楚。）
现有一个多叉树状网络，网络中有三种设备：交换机、电脑和打印机，其中电脑和打印机只存在于叶子节点中。每个节点的孩子是有序的，序号以端口号的形式给出（注意要考虑到现实中可能不是所有的端口号都有设备连接，所以端口号不一定是从1开始的连续自然数）
要求：求出离给出电脑最近的打印机编号，如果有多个符合条件的打印机，则按“前序遍历”的顺序输出最小的打印机。
输入：
第一行输入设备数n。
第2~n+1行按“设备编号 父节点编号 设备类型 设备端口号”的格式给出每个设备的信息。
第n+2行给出询问的电脑设备编号。
输出：
第一行输出满足要求的打印机编号。
第二行输出从所询问的电脑到打印机的路径，节点之间用空格连接。
（应该不能有多余空格）
（样例见代码注释）
解
本题给出的是从子节点到父节点的输入，因此建树语句需要有些区别。
所谓“寻找最近叶子节点”，实际上就是计算目标叶子节点到每一个打印机叶子节点的距离，实际上就是寻找目标叶子节点到每一个打印机叶子节点的最近的共同祖先节点。
代码如下所示：
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#define MAXN 1000
// 假设端口数和设备数都最大为1000
// 要考虑有可能设备的端口并未连接的情况
// 设备号从1开始，端口号从1开始
using namespace std;
/*
假设根节点的父亲节点编号为0，端口号为1
10
1 0 1 1
2 1 1 1
3 1 1 3
4 1 1 5
5 2 3 1
6 2 2 2
7 2 3 4
8 3 2 1
9 3 2 4
10 4 3 1
6
*/
/*
6
1 0 1 1
2 1 1 1
3 1 1 2
4 2 3 1
5 3 1 1
6 5 2 1
6
*/
struct node
{
int children[MAXN] = {0};
int maxport;
int parent = 0;
// int type; // 1:交换机 2：电脑 3：打印机
int pre;
} devices[MAXN];
vector<int> printer;
int n;
int index;
void preorder(int root)
{
index++;
devices[root].pre = index;
for (int i = 1; i <= devices[root].maxport; i++)
{
int c = devices[root].children[i];
if (c != 0)
{
preorder(c);
}
}
}
int distance(int c, int a)
{
int ci = 0, ai = 0;
int _c = c,
_a = a;
while (devices[_c].parent != 0)
{
_c = devices[_c].parent;
ci++;
}
while (devices[_a].parent != 0)
{
_a = devices[_a].parent;
ai++;
}
int cmta = ci - ai;
int count = 0;
_c = c, _a = a;
if (cmta >= 0)
{
while (cmta != 0)
{
_c = devices[_c].parent;
cmta--;
count++;
}
}
else
{
while (cmta != 0)
{
_a = devices[_a].parent;
cmta++;
count++;
}
}
while (_c != _a)
{
_c = devices[_c].parent;
_a = devices[_a].parent;
count++;
count++;
}
return count;
}
void printpath(int c, int a)
{
stack<int> s;
int ci = 0, ai = 0;
int _c = c,
_a = a;
while (devices[_c].parent != 0)
{
_c = devices[_c].parent;
ci++;
}
while (devices[_a].parent != 0)
{
_a = devices[_a].parent;
ai++;
}
int cmta = ci - ai;
_c = c, _a = a;
if (cmta >= 0)
{
while (cmta != 0)
{
cout << _c << " ";
_c = devices[_c].parent;
cmta--;
}
}
else
{
while (cmta != 0)
{
s.push(_a);
_a = devices[_a].parent;
cmta++;
}
}
while (_c != _a)
{
cout << _c << " ";
_c = devices[_c].parent;
s.push(_a);
_a = devices[_a].parent;
}
cout << _a << " ";
while (!s.empty())
{
cout << s.top();
if (!s.empty())
{
cout << " ";
}
s.pop();
}
}
int main()
{
cin >> n;
//build
for (int i = 0; i < n; i++)
{
int id, parent, type, port;
cin >> id >> parent >> type >> port;
devices[parent].children[port] = id;
devices[parent].maxport = max(devices[parent].maxport, port);
if (type == 3)
{
printer.push_back(id);
}
devices[id].parent = parent;
}
preorder(1);
int q;
cin >> q;
int mindis = MAXN;
int minpre = MAXN;
int mini = MAXN;
for (int i = 0; i < printer.size(); i++)
{
int dis = distance(q, printer[i]);
if (dis < mindis)
{
mindis = dis;
minpre = devices[printer[i]].pre;
mini = printer[i];
}
else if (dis == mindis)
{
if (devices[printer[i]].pre < minpre)
{
minpre = devices[printer[i]].pre;
mini = printer[i];
}
}
}
cout << mini << endl;
printpath(q, mini);
return 0;
}问了bzb，说机试题一般不会太讲究复杂度，也就是说能做出来就ok。
我被cue了！