【题目来源】
【题目描述】
给定一棵树，其中 1 号结点是根结点，问哪一个结点的孙子结点最多，有多少个。（孙子结点，就是儿子结点的儿子结点。）
【输入格式】
第一行一个整数 N（N≤10000），表示树结点的个数。
此后 N 行，第 i 行包含一个整数 Ci，表示 i 号结点儿子结点的个数，随后共 Ci 个整数，分别表示一个 i 号结点的儿子结点（结点编号在 1~N 之间）。
【输出格式】
一行两个整数，表示孙子结点最多的结点，以及其孙子结点的个数，如果有多个，输出编号最小的（本题测试数据确保有解）。
【输入样例】
5
2 2 3
1 4
0
1 5
0
【输出样例】
1 1
【数据范围】
N≤10000
【算法分析】
● 孙子节点的界定
孙子结点，就是儿子结点的儿子结点。在上图中，节点 1 的孙子节点为节点 2，节点 2 的孙子节点为节点 3、4、5，节点 3 无孙子节点，节点 4 无孙子节点，节点 5 的孙子节点为节点 6，节点 6 无孙子节点。
● 链式前向星、邻接表
链式前向星：
邻接表（无向无权图）：
邻接表（有向无权图）：
● 链式前向星在算法竞赛中是最常用的图存储方法，尤其在处理大规模稀疏图时，其空间和时间效率优势显著。邻接表虽简单直观，但在竞赛中已逐渐被链式前向星取代。
● 注意：由于无权图的邻接表代码简单直观，所以在处理无权图时，可以选择邻接表。
【算法代码一：邻接表】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e+5;
vector<int> v[maxn];
int idx,imax=INT_MIN;
int n,cnt,x;int main() {cin>>n;for(int i=1; i<=n; i++) {cin>>cnt;while(cnt--) {cin>>x;v[i].push_back(x);}}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
2 2 3
1 4
0
1 5
0out:
1 1
*/
【算法代码二：链式前向星】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e+5;
int e[maxn],ne[maxn],h[maxn],idx;
int id,imax=INT_MIN;
int n,cnt,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>>cnt;while(cnt--) {cin>>x;add(i,x);}}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
2 2 3
1 4
0
1 5
0out:
1 1
*/
【参考文献】