题解：洛谷 P2018 消息传递

【题目来源】洛谷P2018 消息传递 - 洛谷【题目描述】巴蜀国的社会等级森严除了国王之外每个人均有且只有一个直接上级当然国王没有上级。如果A AA是B BB的上级B BB是C CC的上级那么A AA就是C CC的上级。绝对不会出现这样的关系A AA是B BB的上级B BB也是A AA的上级。最开始的时刻是0 00你要做的就是用1 11单位的时间把一个消息告诉某一个人让他们自行散布消息。在任意一个时间单位中任何一个已经接到消息的人都可以把消息告诉他的一个直接上级或者直接下属。现在你想知道到底需要多长时间消息才能传遍整个巴蜀国的所有人要使消息在传递过程中消耗的时间最短可供选择的人有哪些【输入】输入文件的第一行为一个整数N NNN ≤ 1000 N\le 1000N≤1000表示巴蜀国人的总数假如人按照1 11到n nn编上了号码国王的编号是1 11。第2 22行到第N NN行共N − 1 N-1N−1行每一行一个整数第i ii行的整数表示编号为i ii的人直接上级的编号。【输出】文件输出共计两行第一行为一个整数表示最后一个人接到消息的最早时间。第二行有若干个数表示可供选择人的编号按照编号从小到大的顺序输出中间用空格分开。【输入样例】8 1 1 3 4 4 4 3【输出样例】5 3 4 5 6 7【算法标签】#普及# #提高#【代码详解】#includebits/stdc.husingnamespacestd;constintN1005,MN*2;intn;inth[N],e[M],ne[M],idx;// 邻接表intcnt[N],ti[N],ans1e9,res;// cnt: 子树大小, ti: 每个节点为根的结果, ans: 最小值, res: 当前根的结果// 添加无向边voidadd(inta,intb){e[idx]b,ne[idx]h[a],h[a]idx;}// 深度优先搜索voiddfs(intu,intfa)// u: 当前节点, fa: 父节点{cnt[u]1;// 包括自己intmaxn0,num0,t0;// maxn: 最大子树大小, num: 最大子树个数, t: 子节点数for(intih[u];~i;ine[i])// 遍历子节点{intve[i];if(vfa)// 跳过父节点{continue;}dfs(v,u);// 递归处理子树t;// 子节点计数if(cnt[v]maxn)// 找到更大的子树{maxncnt[v];num1;}elseif(cnt[v]maxn)// 相同大小的子树{num;}}// if (fa) t; // 如果考虑父节点方向tmax(t,maxnnum-1);// 计算所需轮数cnt[u]t;// 更新当前节点的完成时间resmax(res,cnt[u]);// 更新全局最大值}intmain(){cinn;// 输入节点数memset(h,-1,sizeof(h));for(inti2;in;i)// 输入边{intx;cinx;add(i,x),add(x,i);// 建树}for(inti1;in;i)// 以每个节点为根计算{memset(cnt,0,sizeof(cnt));// 重置计数数组res0;// 重置结果dfs(i,0);// 从节点i开始DFSti[i]res;// 记录以i为根的结果ansmin(ans,ti[i]);// 更新最小值}coutansendl;// 输出最小结果for(inti1;in;i)// 输出所有达到最小值的根节点{if(ti[i]ans){couti ;}}coutendl;return0;}【运行结果】8 1 1 3 4 4 4 3 5 3 4 5 6 7