东方博宜OJ 1776：谁的孙子最多 II ← 邻接表 or 链式前向星

【题目来源】
https://oj.czos.cn/p/1776

【题目描述】
给定一棵树，其中 1 号结点是根结点，问哪一个结点的孙子结点最多，有多少个。（孙子结点，就是儿子结点的儿子结点。）

【输入格式】
第一行一个整数 N（N≤10000），表示树结点的个数。
此后 N-1 行，第 i 行包含一个整数 fi，表示 i+1 号结点的父亲。

【输出格式】
一行两个整数，表示孙子结点最多的结点，以及其孙子结点的个数，如果有多个，输出编号最小的。

【输入样例】
5
1
1
2
4

【输出样例】
1 1

【数据范围】
N≤10000

【算法分析】
● 孙子节点的界定

孙子结点，就是儿子结点的儿子结点。在上图中，节点 1 的孙子节点为节点 2，节点 2 的孙子节点为节点 3、4、5，节点 3 无孙子节点，节点 4 无孙子节点，节点 5 的孙子节点为节点 6，节点 6 无孙子节点。

● 链式前向星、邻接表
链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
邻接表（无向无权图）：https://blog.csdn.net/hnjzsyjyj/article/details/101233779
邻接表（有向无权图）：https://blog.csdn.net/hnjzsyjyj/article/details/101233485

● 链式前向星在算法竞赛中是‌最常用‌的图存储方法，尤其在处理大规模稀疏图时，其空间和时间效率优势显著。邻接表虽简单直观，但在竞赛中已逐渐被链式前向星取代。

● 注意：由于无权图的邻接表代码简单直观，所以在处理无权图时，可以选择邻接表。

● 本题与“东方博宜1775”（https://blog.csdn.net/hnjzsyjyj/article/details/155704891）的不同点仅在于输入格式的不同，其他一样。

【算法代码一：邻接表】

#include<bits/stdc++.h>
using namespace std;const int maxn=1e4+5;
vector<int> v[maxn];
int idx,imax=INT_MIN;
int n,x;int main() {cin>>n;for(int i=1; i<n; i++) {cin>>x;v[x].push_back(i+1);}for(int i=1; i<=n; i++) {int sum=0;for(int j=0; j<v[i].size(); j++) {int t=v[i][j];sum+=v[t].size();}if(sum>imax) {imax=sum;idx=i;}}cout<<idx<<" "<<imax;return 0;
}/*
in:
5
1
1
2
4out:
1 1
*/

【算法代码二：链式前向星】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e4+5;
int e[maxn],ne[maxn],h[maxn],idx;
int id,imax=INT_MIN;
int n,x;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int main() {memset(h,-1,sizeof h);cin>>n;for(int i=1; i<n; i++) {cin>>x;add(x,i+1);}for(int i=1; i<=n; i++) {int sum=0;for(int j=h[i]; j!=-1; j=ne[j]) {int t=e[j];for(int k=h[t]; k!=-1; k=ne[k]) sum++;}if(sum>imax) {imax=sum;id=i;}}cout<<id<<" "<<imax;return 0;
}/*
in:
5
1
1
2
4out:
1 1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/155679814
https://blog.csdn.net/hnjzsyjyj/article/details/155690173
https://blog.csdn.net/hnjzsyjyj/article/details/152726091
https://blog.csdn.net/hnjzsyjyj/article/details/152729089
https://blog.csdn.net/chensimiao0717/article/details/143650804
https://mybzjq.blog.csdn.net/article/details/137256161