问题描述
给定一个公司的网络，由n台交换机和m台终端电脑组成，交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置，编号为1的交换机为根交换机，层级为1。其他的交换机都连接到一台比自己上一层的交换机上，其层级为对应交换机的层级加1。所有的终端电脑都直接连接到交换机上。
当信息在电脑、交换机之间传递时，每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问，电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。
输入格式
输入的第一行包含两个整数n, m，分别表示交换机的台数和终端电脑的台数。
第二行包含n - 1个整数，分别表示第2、3、……、n台交换机所连接的比自己上一层的交换机的编号。第i台交换机所连接的上一层的交换机编号一定比自己的编号小。
第三行包含m个整数，分别表示第1、2、……、m台终端电脑所连接的交换机的编号。
输出格式
输出一个整数，表示消息传递最多需要的步数。
样例输入
4 2
1 1 3
2 1
样例输出
3
样例说明
样例的网络连接模式如下，其中圆圈表示交换机，方框表示电脑：
其中电脑1与交换机4之间的消息传递花费的时间最长，为4个单位时间。
样例输入
4 4
1 2 2
3 4 4 4
样例输出
4
样例说明
样例的网络连接模式如下：
其中电脑1与电脑4之间的消息传递花费的时间最长，为4个单位时间。
评测用例规模与约定
前30%的评测用例满足：n ≤ 5, m ≤ 5。
前50%的评测用例满足：n ≤ 20, m ≤ 20。
前70%的评测用例满足：n ≤ 100, m ≤ 100。
所有评测用例都满足：1 ≤ n ≤ 10000，1 ≤ m ≤ 10000。
1 #include <iostream> 2 #include <vector> 3 #include <math.h> 4 #include <map> 5 6 using namespace std; 7 8 int max=0; //最大延时 9 class node 10 { 11 private: 12 int no; //节点标号 13 int type; //类型，1为路由，2为电脑 14 vector<node*> v; //下级节点表 15 map<int,pair<int,node*>> map1; //key是电脑编号，pair－key是总跳数，pair－value是所属节点地址 16 public: 17 node(int no, int type ) : no(no), type(type){ } 18 19 20 int getNo() { 21 return no; 22 } 23 void add(node* n) 24 { 25 v.push_back(n); 26 } 27 28 int getType() const { 29 return type; 30 } 31 32 map<int,pair<int,node*>>* echo() //发送消息，计算最大延迟，将路由表返回上一级路由 33 { 34 for(int i=0;i<v.size();i++) //对所有下级节点获取信息并更新至本路由表 35 { 36 map<int,pair<int,node*>>* temp = v[i]->echo(); 37 for(map<int,pair<int,node*>>::iterator it = temp->begin();it!=temp->end();it++) 38 { 39 int noo = it->first; 40 pair<int,node*> p2 = pair<int,node*>(it->second.first,it->second.second); 41 map1.insert(pair<int,pair<int,node*>>(noo,p2)); 42 } 43 } 44 for(int i=0;i<v.size();i++) //对本层电脑进行搜索，更新路由表 45 if(v[i]->getType()==2) 46 { 47 int noo = v[i]->getNo(); 48 pair<int,node*> p2 = pair<int,node*>(1,v[i]); 49 map1.insert(pair<int,pair<int,node*>>(noo,p2)); 50 } 51 int max1(0),max2(0); //设置最值进行计算 52 node* no1 = NULL; //纪录第一个最大值 53 for(map<int,pair<int,node*>>::iterator it = map1.begin();it!=map1.end();it++) 54 { 55 if(it->second.first>max1) //搜索一个最大值，并纪录值和属于哪个路由 56 { 57 max1 = it->second.first; 58 no1 = it->second.second; 59 } 60 } 61 for(map<int,pair<int,node*>>::iterator it = map1.begin();it!=map1.end();it++) 62 { 63 //cout<<"node "<<no<<" com "<<it->first<<" count "<<it->second.first<<" from "<<it->second.second->getNo()<<endl; 64 if(it->second.first<=max1 && it->second.first>max2 && it->second.second != no1) //纪录第二个最大值，必须和第一个来自不同路由避免重复计算 65 { 66 max2 = it->second.first; 67 } 68 it->second.first++; //更新跳数以及来自哪个节点 69 it->second.second=this; 70 } 71 if(max1+max2>::max){ //更新最大延时 72 ::max=max1+max2;//cout<<::max<<endl; 73 } 74 return &map1; //返回路由表 75 }; 76 }; 77 int main() { 78 map<int,node*> j; 79 map<int,node*> computer; 80 int n,m; 81 cin>>n>>m; 82 node* root = new node(1,1); 83 j[1] = root; 84 for(int i=2;i<=n;i++) //读取节点 85 { 86 int a; 87 cin>>a; 88 node* pp = new node(i,1); 89 j[a]->add(pp); 90 j[i] = pp; 91 } 92 for(int i=1;i<=m;i++) //读取电脑 93 { 94 int a; 95 cin>>a; 96 node* pp = new node(i,2); 97 j[a]->add(pp); 98 computer[i]=pp; 99 } 100 root->echo(); //根节点发送消息 101 cout<<::max; 102 103 return 0; 104 }