Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

D. Penchick and Desert Rabbit time limit per test: 3 seconds memory limit per test: 256…

  1. User

    D. Penchick and Desert Rabbit

    time limit per test: 3 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    题目描述

    离 Penchick 和 Chloe 前往新加坡的时间只剩下几个小时了,他们迫不及待地想去看看新加坡植物园的参天大树!为了抑制激动的心情,Penchick 制作了一棵扎根树,让 Chloe 和他自己忙个不停。

    彭奇克有一棵有根树 ∗∗ ,由 nn 个顶点组成,编号从 11 到 nn ,顶点 11 是根,克洛伊可以选择一个非负整数 dd 来创建一棵深度为 dd 的完美二叉树 †† 。

    由于彭希克和克洛伊是好朋友,克洛伊希望自己的树与彭希克的树同构 ‡‡ 。为了满足这个条件,克洛伊可以在自己的树上执行以下操作,次数不限:

    • 选择一条边 (u,v)(u,v) ,其中 uu 是 vv 的父边。
    • 删除顶点 vv 和所有连接到 vv 的边,然后将 vv 之前的所有子代直接连接到 uu 。

    具体来说,在 vv 为叶子的边 (u,v)(u,v) 上进行操作将删除顶点 vv ,而不会添加任何新的边。

    由于构建完美二叉树非常耗时,克洛伊希望选择最小值 dd ,这样深度为 dd 的完美二叉树就可以通过上述操作与彭希克的树同构。注意,她不能改变树的根。

    ∗∗ 树是没有循环的连通图。有根的树是指有一个顶点是特殊的,叫做根。顶点 vv 的父顶点是从 vv 到根的简单路径上的第一个顶点。根没有父顶点。顶点 vv 的子顶点是以 vv 为父顶点的任意顶点 uu 。叶是任何没有子顶点的顶点。

    †† 一棵完整的二叉树是有根的树,其中每个节点都有 00 或 22 个子节点。完全二叉树是指每片叶子与根的距离都相同的完全二叉树。树的深度就是树根到树叶的距离。

    ‡‡ 如果存在顶点的排列 pp ,使得当且仅当边 (pu,pv)(pu,pv) 存在于第二棵树时,边 (u,v)(u,v) 存在于第一棵树,并且 r1=pr2r1=pr2 存在于第二棵树,那么两棵分别根植于 r1r1 和 r2r2 的树被认为是同构的。

    输入格式

    每个测试包含多个测试用例。第一行包含测试用例的数量 tt ( 1≤t≤1051 \le t \le 10^5 )。测试用例说明如下。

    每个测试用例的第一行都包含一个整数 nn ( 2≤n≤1062 \le n \le 10^6 ) - 彭奇克树的顶点数。

    每个测试用例的第二行包含 n−1n-1 个整数 p2,p3,…,pnp_2, p_3, \ldots, p_n ( 1≤pi≤i−11 \leq p_i \leq i-1 ) - 顶点 ii 的父节点。

    保证所有测试用例中 nn 的总和不超过 10610^6 。

    输出格式

    对于每个测试用例,每行输出一个整数:克洛伊完美二叉树的最小深度。

    样例 #1

    样例输入 #1

    5
    6
    1 2 2 1 1
    15
    1 1 2 2 3 3 4 4 5 5 6 6 7 7
    5
    1 2 2 2
    7
    1 1 2 1 1 2
    10
    1 1 1 2 2 2 4 3 3
    

    样例输出 #1

    2
    3
    3
    3
    3
    

    提示

    注

    对于第一个测试用例,创建一棵深度为 22 的完美二叉树。

    [image] open

    考虑对边 ACAC 进行操作。然后删除边 ACAC 、 CFCF 和 CGCG ,添加边 AFAF 和 AGAG 。

    [image] open

    生成的树与输入的树同构。可以证明,在一棵深度小于 22 的二叉树上进行的任何操作序列都不会导致一棵与输入所给树同构的树。

    在第二个测试案例中,树已经与深度为 33 的完美二叉树同构。

    用c++写,并解释代码和思路,用中文。

  2. Assistant

    要解决这个问题,我们需要找到克洛伊创建的完美二叉树的最小深度 ( d ),使得经过若干次操作后,这棵完美二叉树可以与彭奇克的树同构。

    问题分析

    首先,我们需要理解题目中的操作。克洛伊可以在自己的完美二叉树上删除某些节点,并将被删除节点的子节点直接连接到其父节点。这相当于将一个拥有多个子节点的节点通过操作重新组织成一个二叉树结构。

    为了找到最小的 ( d ),我们可以采用以下策略:

    1. 递归计算每个节点的深度需求:

      • 对于每个节点,首先计算其所有子节点的深度。
      • 将这些深度按照降序排序。
      • 依次将这些子节点分配到左子树和右子树,确保深度的平衡。
      • 节点的深度需求为其左右子树深度的最大值加一。
    2. 采用深度优先搜索(DFS):

      • 我们可以通过DFS遍历树,并应用上述策略来计算每个节点的深度需求。
      • 最终根节点的深度需求即为所需的最小 ( d )。

    算法步骤

    1. 输入处理:

      • 对于每个测试用例,读取节点数 ( n ) 和父节点数组。
      • 构建树的邻接表表示。
    2. 深度计算:

      • 从根节点(节点1)开始,使用DFS递归计算每个节点的深度需求。
      • 对于叶子节点,深度为0。
      • 对于内部节点,按照深度降序排序子节点的深度,交替分配到左右子树,并计算当前节点的深度。
    3. 输出结果:

      • 对于每个测试用例,输出根节点的深度需求,即所需的最小 ( d )。

    代码实现

    以下是基于上述策略的C++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    // Fast IO
    struct fast_io {
        fast_io() {
            ios::sync_with_stdio(false);
            cin.tie(NULL);
        }
    } fio;
    
    // Function to compute depth using DFS
    int compute_depth(int u, const vector<vector<int>> &children) {
        if (children[u].empty()) {
            return 0;
        }
        vector<int> child_depths;
        for(auto &v : children[u]){
            child_depths.push_back(compute_depth(v, children));
        }
        // Sort depths in descending order
        sort(child_depths.begin(), child_depths.end(), greater<int>());
        // Assign to left and right alternately
        int left_depth = 0, right_depth = 0;
        for(int i=0; i<child_depths.size(); ++i){
            if(i%2 == 0){
                left_depth = max(left_depth, child_depths[i]);
            }
            else{
                right_depth = max(right_depth, child_depths[i]);
            }
        }
        return max(left_depth, right_depth) +1;
    }
    
    int main(){
        int t;
        cin >> t;
        while(t--){
            int n;
            cin >> n;
            vector<int> parents(n+1, 0); // 1-based indexing
            vector<vector<int>> children(n+1, vector<int>());
            for(int i=2; i<=n; ++i){
                cin >> parents[i];
                children[parents[i]].push_back(i);
            }
            // Compute depth starting from root (1)
            int d = compute_depth(1, children);
            cout << d << "\n";
        }
    }
    

    代码解释

    1. 快速输入输出:

      • 使用ios::sync_with_stdio(false);和cin.tie(NULL);来加速输入输出操作,以应对大量测试用例。
    2. 树的表示:

      • 使用邻接表(children向量)来表示树,其中children[u]存储节点u的所有子节点。
    3. 深度计算函数compute_depth:

      • 递归地计算每个节点的深度:
        • 如果节点没有子节点(叶子节点),深度为0。
        • 否则,先计算所有子节点的深度,并将这些深度按降序排序。
        • 然后,交替将这些深度分配到左子树和右子树,计算左右子树的最大深度。
        • 当前节点的深度需求为左右子树深度的最大值加一。
    4. 主函数:

      • 读取测试用例数$t$。
      • 对于每个测试用例:
        • 读取节点数$n$和父节点数组。
        • 构建树的邻接表。
        • 通过调用compute_depth函数计算根节点的深度需求。
        • 输出结果。

    示例验证

    以样例输入的第一个测试用例为例:

    • 树结构:
          1
         / | \
        2 4 5
       / \
      3   6
      
    • 计算过程:
      • 叶子节点(3,4,5,6)的深度为0。
      • 节点2的子节点(3,6)的深度为0,排序后:[0,0]。
        • 分配到左和右子树:左深度=0,右深度=0。
        • 节点2的深度= max(0,0)+1=1。
      • 节点1的子节点(2,4,5)的深度分别为1,0,0,排序后:[1,0,0]。
        • 分配到左和右子树:左深度=1,右深度=0。
        • 节点1的深度= max(1,0)+1=2。
      • 输出为2,与样例输出一致。

    结论

    通过递归地计算每个节点的深度需求,并合理分配子节点到左右子树,我们可以有效地找到克洛伊所需创建的最小深度 ( d ),确保经过若干次操作后,两棵树同构。