点击蓝字
关注赵码匠
（说明：输入第一行为结点个数n，第二行为n-1个整数，依次表示结点2~n的父结点编号，满足2≤n≤100000且1≤fa[i]<i，根结点为1。）
意料之外，第三题的程序代码非常短，其核心思想就是第9~16行的循环，并且可以结合第31题来推测程序功能：
显然排除掉C和D，程序在计算的一定是路径，这里也可以通过第13~15行的判断来佐证：
if (f[i] + 1 > f[fa[i]]) {f[fa[i]] = f[i] + 1;}
转化为伪代码就是“f[父节点] = f[子节点] + 1”，这是非常标准的树上求路径的状态转移，本题的状态转移为：
如果从父节点出发的路径，没有先到子节点再出发的路径长，则更新路径长度，其中的“+1”为父节点到子节点的路径长度1。
据此，我们推测f[i]记录从节点i出发的最长路径长度，那么到底是什么路径呢？需要回头看都10~12行的判断。
这里的判断为：如果从父节点出发的路径+子节点出发的路径+1大于记录的答案，则更新答案。
其中，这里的+1大概率是从父节点到达子节点的路径1，而想要和最大，两个路径不一定重合，因为父节点有多个孩子，f[fa[i]]对应的路径不一定经过i。
因此，f[fa[i]]+f[i]+1的路径含义为：从父节点出发的一条路径+子节点的路径+1。
而f[i]数组的含义，在这时也可以知道了：表示从节点i出发，向叶子节点走的最长距离。
再回到表达式，如何让该路径之和最大呢？在树结构中，最长的一条路径被称为“树的直径”，因此可以推测最终ans的值就是这棵树的直径，也就是31题选项A的描述。
最后，回到第9行的循环，为什么要从n到2逆序遍历更新所有节点呢？
由于输入保证fa[i]<i，因此在遍历到节点i时，它的所有子节点路径都已经更新完毕，从而保证f[i]当前记录的一定是最长路径；
而对于f[fa[i]]来说，由于还没有第13~15行用f[i]更新该值，因此f[fa[i]]当前记录的是除了节点i以外，其他子节点分支中最长的一条路径。
28. 当n=5，fa[2]~fa[5]={1,2,3,4}时，程序输出4。
答案：√
解析：首先绘制出对应的树：
该树退化为了链，并且由于数据较少，我们可以模拟一下代码来验证结论：
（0）初始情况：f[1]=f[2]=f[3]=f[4]=f[5]=0，ans=0；
（1）开始循环：i=5时，距离=f[4]+f[5]+1=0+0+1>ans，因此ans=1；再更新f[4]=f[5]+1=1；
（2）i=4时，距离=f[3]+f[4]+1=0+1+1>ans，因此ans=2；再更新f[3]=f[4]+1=2；
（3）i=3时，距离=f[2]+f[3]+1=0+2+1=3>ans，因此ans=3；再更新f[2]=f[3]+1=3；
（4）i=2时，距离=f[1]+f[2]+1=0+3=1=4>ans，因此ans=4；再更新f[1]=f[2]+1=4；
（5）循环结束，最终输出ans=4。
29. 程序输出前，f[1]的值一定等于ans的值。
答案：×
解析：根据前面的分析，f[1]的值为从节点1出发的最长路径，而ans为树的直径，显然不相等，因为直径有可能不经过节点1，并且可能存在ans>f[1]的情况。
30. 将第10~12行与第13~15行两个if语句的顺序交换后，程序的输出结果不受影响。
答案：×
解析：交换前，程序先利用当前f[i]值更新答案，再更新父节点的距离；
交换后，程序先更新父节点的距离，再利用当前f[i]值更新答案。
由于交换后，可能会出现将fa[i]的f值更新为经过当前节点i的距离f[i]+1，从而导致后续计算出来ans对应路径会经过两次节点i，这就与原本ans表示直径的定义不同，因此程序的输出结果可能会变化。
再深挖一下，结果边变小还是变大呢？先直接告诉答案：最终输出结果可能会变大。
交换后，假如每次让f[fa[i]]更新为f[i]+1，那么每次记录的ans的路径，等价于从fa[i]出发向下走到底再回来，显然有可能比真实的直径大。（例如树退化为链的情况）
31. 程序输出的ans表示的是（ ）
A、树中距离最远的两个结点之间路径所经过的边数
B、根结点1到最远叶子结点之间路径所经过的边数
C、树中叶子结点的个数
D、所有结点的父结点编号之和
答案：A
解析：见做题前的分析。
32. 当n=7, fa[2]~fa[7]={1,1,2,2,3,3}时，输出为（ ）
A、2
B、3
C、4
D、5
答案：C
解析：直接根据数据画出对应的树：
该树最长的路径之一为4→2→1→3→7，因此树的直径为4，即输出的ans=4。
33. 当n=10，满足输出为9的合法输入种类数为（ ）
A、0
B、9
C、256
D、512
答案：C
解析：对于一棵10个节点的树来说，它有9条边，而最终输出ans=9，说明树的直径，或者说最长路径一定是遍历了所有的边。
那么，什么形状的树，它的最长路径为所有边都走一遍呢？显然只有一种可能性：这棵树的形状为一条链。
为什么说是形状呢？因为根节点1的位置不确定，因此以节点1为根的话，其形态不一定是链，但是可以将其拉成链。
因此，我们将输入种类数，变成了一个排列组合问题：在一条链上，如何分配节点2~10，使其保持为一条链。
由于题干约束了“fa[i]<i”，因此当节点1一侧的节点分配完毕后，它的排列只可能是有序这一种情况。
因此，问题又转变为了：2~10这9个节点，如何分配到节点1的左侧或右侧？这里有2种解决思路：
方法1
（1）节点2只能接在节点1后面，即fa[2]=1，因此只有1种可能性；
（2）节点3可以节点1或2后面，即fa[3]=1或fa[3]=2，因此有2种可能性；
（3）再加入节点4，当前{1,2,3}组成的树肯定是链，而节点4必须接在某个端点上，因此也只有2种可能性；
（4）节点5~10都以此类推……
最终的总可能情况为1*2*2*2*...*2=1*2^8=256。
方法2
每个节点都可能在节点1的左侧或右侧，因此总共有2^9=512种可能性；
但是由于题干中的树不分形态，即“2-1-3”和“3-1-2”算同一种，因此所有情况需要除以2，即512÷2=256种情况。
原创文章制作不易
欢迎大家分享到微信群、朋友圈等社交圈
如需转载，可后台留言开通白名单
注：未经允许不得私自搬运到其他平台
如果觉得写的不错的话
还请帮忙点赞、在看、关注
谢谢!
