5 条题解

  • 21
    @ 2023-8-1 17:13:49

    这道题的解决思路如下:

    1. 构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用于表示树的结构。然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中。
    2. 遍历树并统计孙子节点数量:从根节点开始,依次遍历树的每个节点。对于每个节点,迭代它的所有子节点,并统计每个子节点的孩子节点数量。累加所有子节点的孩子节点数量,即得到当前节点的孙子节点数量。
    3. 寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号。如果找到了孙子节点数量更大的节点,则更新最大数量和对应的节点编号。
    4. 输出结果:输出最大孙子节点数量和对应的节点编号。

    示例代码已经给出,以下是对代码的解析:

    • 首先读取输入的树的节点数量 n。
    • 创建一个二维向量 tree,大小为 n+1,用于存储树的结构。
    • 循环读取 n-1 条边的信息,将每个子节点添加到对应父节点的向量中。
    • 初始化最大孙子节点数量为 0,最大孙子节点对应的节点编号为 1。
    • 遍历整个树,对于每个节点,计算其孙子节点数量:
      • 迭代当前节点的所有子节点,在子节点的向量中统计孩子节点的数量,并累加到当前节点的孙子节点数量上。
    • 如果当前节点的孙子节点数量大于最大孙子节点数量,则更新最大孙子节点数量和对应的节点编号。
    • 输出最大孙子节点数量和对应的节点编号。
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
    
        vector<vector<int> > tree(n + 1);
    
        for (int i = 2; i <= n; i++) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
        }
    
        int max_grandchildren_count = 0;
        int max_node = 1;
    
        for (int i = 1; i <= n; i++) {
            int grandchildren_count = 0;
            for (size_t j = 0; j < tree[i].size(); j++) {
                int child = tree[i][j];
                grandchildren_count += tree[child].size();
            }
            if (grandchildren_count > max_grandchildren_count) {
                max_grandchildren_count = grandchildren_count;
                max_node = i;
            }
        }
    
        cout << max_node << " " << max_grandchildren_count << endl;
    
        return 0;
    }
    
    • @ 2023-8-5 22:31:20

      你ac过了吗?就来这里显摆?

    • @ 2023-8-6 20:17:04

      没有过你发它有什么用?????@

    • @ 2023-8-6 20:17:30

      别以为自己很厉害@

    • @ 2023-8-6 20:17:53

      我是来搞笑的?你是来干啥的?充当大佬的?@

    • @ 2023-8-6 20:18:30

      还有我看你的题解你管得着吗@

    • @ 2023-8-7 8:10:49

      @ 请问你试过没有就过来抹黑他人

      image

      人家发题解是为了供大家参考学习的,并不是你口中所说的炫耀

    • @ 2023-8-7 10:28:06

      @ 别以为自己很牛,跑这里来说东说西

    • @ 2023-10-22 21:10:55

      @ 不要当猴子

    • @ 2023-11-5 15:47:06

      题解区这是吵上了吗???

    • @ 2023-12-3 11:27:44

      @ 拜托,本来就是AC的好不好! 网址:记录详情 - 核OJ_核桃编程 (hetao101.com)

    • @ 2023-12-5 22:19:29

      那家xxs,网络上这么横行霸道,现实中自卑无能?🤣🤣🤣👉🤡🤡🤡@

    • @ 2024-2-19 18:02:55

      看着评论区一脸无语……

    • @ 2024-2-19 18:09:25

      设身处地的想想,一个刚刚来核桃编程半年的人,正百无聊赖的翻看着题解,希望寻求一个答案,这时,他猛然看见很多大佬在评论区里喷人,然后连忙关闭了评论区……

    • @ 2024-2-19 18:22:47

      没有人发现那个人就是我吧

    • @ 2024-2-22 19:40:59

      大家做题的气氛都被你搅没了@

    • @ 2024-2-22 19:40:59

      大家做题的气氛都被你搅没了@

    • @ 2024-2-22 19:41:00

      大家做题的气氛都被你搅没了@

    • @ 2024-4-20 11:22:14

      这咋还吵起来了?

    • @ 2024-6-1 11:34:37

      @ 这个哥们怕不是用python编译的

  • 8
    @ 2023-7-23 16:58:50

    本题较为基础,只需要正常对该有根树进行存储,存储完每个节点后,按照节点编号循环枚举统计每个节点的孙子节点,找到孙子节点最多的节点编号及孙子节点的个数即可。

    参考代码
    //cnt统计孙子节点数量,ans记录最多的孙子节点数量,xh记录孙子节点最多的节点编号
    int cnt = 0, ans = 0, xh;
    	for (int i = 1; i <= n; i++)
    	{
            cnt = 0;
            for (int j = 0; j < e[i].size(); j++)
    			cnt += e[e[i][j]].size();
            if (cnt > ans)
            {
                ans = cnt;
                xh = i;
            }
        }
    
    • @ 2024-5-4 21:36:38

      你这用max函数不行吗,还整那么复杂

    • @ 2024-5-4 21:45:00

      哦,我搞错了,对不起

  • 4
    @ 2023-8-6 20:16:49

    核心思想:

    for(int j=0;j<e[i].size();j++)
        sum+=e[e[i][j]].size(); // e[e[i][j]]是e[i]的儿子节点,统计儿子节点的儿子节点个数
    
    • 1
      @ 2024-1-29 17:00:50
      #include <bits/stdc++.h>
      using namespace std;
      const int MAXN = 1005; //我还是这么写了,虽然感觉没啥用,但毕竟课上这么写
      vector <int> e[MAXN];//只存子节点即可
      int sum;
      int ans;
      int pos_ans =  -1;//编号
      void dfs(int u);//函数声明,如果把函数写前面就不用写
      int main()
      {
      int n;
      cin >> n;
      for (int i = 1;i <= n - 1;i++)
      {
      int U,V;
      cin >> U >> V;
      e[U].push_back(V);
      }
      dfs(1);
      cout << pos_ans << " " << ans << "\n";
      return 0;
      }
      void dfs(int u)
      {
      sum = 0;
      for (int i = 0;i < (int)e[u].size();i++)
      {
      sum += (int)e[e[u][i]].size();//这里必须强制转换
      }
      if (sum > ans)//如果找到更优方案
      {
      ans = sum;
      pos_ans = u;
      }
      else if (sum == ans)//如果两方案一样优
      {
      pos_ans = min(pos_ans,u);//取更小一个的序号
      }
      for (int i = 0;i < (int)e[u].size();i++)//呜呜,这里当时把0不小心打成了1,只有50分,害我检查了将近一个点
      {
      dfs(e[u][i]);//遍历
      }
      return;
      }
      

      的的确确已经AC—–c++14(O2)

      • -28
        @ 2023-8-6 20:41:14

        题解没有完整的,我来替补^__^(背地十分无语) 感谢王浩冉的解题思路 下面正片开始 这道题的解决思路如下:

        1. 构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用于表示树的结构。然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中。
        2. 遍历树并统计孙子节点数量:从根节点开始,依次遍历树的每个节点。对于每个节点,迭代它的所有子节点,并统计每个子节点的孩子节点数量。累加所有子节点的孩子节点数量,即得到当前节点的孙子节点数量。
        3. 寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号。如果找到了孙子节点数量更大的节点,则更新最大数量和对应的节点编号。
        4. 输出结果:输出最大孙子节点数量和对应的节点编号。 ok,正片结束,上代码!
        #include <iostream>
        #include <vector>
        /*思路.1、构建树的数据结构:首先创建一个包含 n+1 个元素的向量,每个元素都是一个空的向量,用
        于表示树的结构.然后按照输入的父子节点关系,将每个子节点添加到对应父节点的向量中.
        2、遍历树并统计孙子节点数量: 从根节点开始,依次遍历树的每个节点.对于每个节点,迭代它的所有
        子节点,共统计每个子节点的孩子节点数量.累加所有子节点的孩子节点数量,即得到当前节点的孙子节
        点数量.
        3、寻找孙子节点最多的节点:在遍历过程中记录当前最大的孙子节点数量和对应的节点编号.如果找到
        了孙子节点数量更大的节点,则更新最大数量和对应的节点编号.
        4、输出结果: 输出最大孙子节点数量和对应的节点编号.
        */
        using namespace std;
        const int MAXN = 1005;
        int n, m;
        vector<int> e[MAXN];//创建一个二维向量 e,用于存储树的结构
        int fa[MAXN];
        int main()
        {
            cin >> n;//输入的树的节点数量n
            for (int i = 1; i<= n - 1; i++)//环 n1 条边的信息,将每个节点添加到对应父节点的向量中
            {
                int u, v;
                cin >> u >> v;
                fa[v] = u;
                e[u].push_back(v);
            }
            int cnt = 0,ans = 0,xh;//初始化最大孙子节点数量为 0,最大孙子节点对应的节点编号为 0
            //遍历整个树,对于每个节点,计算其孙子节点数量
            for (int i = 1; i <= n; i++)
            {
                //选代当前节点的所有子节点,在子节点的向量中统计孩子节点的数量,并累加到当前节点的孙子
        节点数量上
                cnt = 0;
                for (int j = 0; j < e[i].size(); j++)
                    cnt += e[e[i][j]].size();
                //如果当前节点的孙子节点数量大于最大孙子节点数量,则更新最大孙子节点数量和对应的节点编
        号
                if (cnt > ans)
                {
                    ans = cnt;
                    xh = i;
                }
            }
            cout<< xh << " " << ans;
        }
        
      • 1

      信息

      ID
      327
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      (无)
      递交数
      656
      已通过
      334
      上传者