题目思路

思路：模拟 + 排序

题目保证两座沙堡的对应序号相同。故前 $n$ 个沙堡无需考虑是否相同的问题。

从明天的第 $n + 1$ 个沙堡开始，为新增的沙堡，这块的沙堡要满足，所有沙堡的父亲沙堡编号都各不相同，所以沙堡的父亲编号都小于等于 $n$ ，因为大于 $n$ 的编号均为明天新增的小沙堡，其不可能作为其他沙堡的父亲沙堡。

为了方便判断是否有两个新增沙堡的父亲沙堡相同，将所有的新增沙堡按其父亲沙堡编号排序，如果两个沙堡的父亲沙堡编号相同，这两个沙堡在排序后必然相邻。

时间复杂度：$O(n\log n)$ 排序的复杂度，因为合法的 $m$ 最多是 $2n$

类似题目推荐

推荐几道排序相关的题目

LeetCode

1.合并两个有序数组

2.最大间距

Codefun2000

1. P1048. 华东师范大学保研机试-2022-整数排序
2. P1281 中国光大银行 2023.05.13-春招-第一题-泡泡排序
3. P1173 京东 2023.04.08-春招-第三题-构造排列
4. P1014 美团 2022.10.8-塔子玩游戏

代码

C++

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> A;
    // 今天的沙堡
    for (int i = 1; i < n; ++i) {
        int j; cin >> j;
        j -= 1;
        A.emplace_back(j);
    }

    int m;
    cin >> m;
    vector<int> B;
    // 明天的沙堡
    for (int i = 1; i < m; ++i) {
        int j; cin >> j;
        j -= 1;
        B.emplace_back(j);
    }

    // 今天的沙堡数量必然小于等于明天的沙堡数量
    if (n > m) {
        cout << "no\n";
        return;
    }

    // 新增的沙堡的父亲沙堡编号全都是 < n 的，且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）
    // 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻
    sort(B.begin() + n - 1, B.end());
    for (int i = n - 1; i < B.size(); ++i) {
        if (B[i] >= n) {
            cout << "no\n";
            return;
        }
        if (i >= n && B[i] == B[i - 1]) {
            cout << "no\n";
            return;
        }
    }

    cout << "yes\n";
}

int main()
{
    int T = 1;
    cin >> T;
    while (T--) solve();

    return 0;
}

python

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    # 今天的沙堡
    for i in range(n - 1):
        A[i] -= 1

    m = int(input())
    B = list(map(int, input().split()))
    # 明天的沙堡
    for i in range(m - 1):
        B[i] -= 1

    # 今天的沙堡数量必然小于等于明天的沙堡数量
    if n > m:
        print("no")
        return

    # 新增的沙堡的父亲沙堡编号全都是 < n 的，且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）
    # 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻
    B[n - 1:] = sorted(B[n - 1:])
    for i in range(n - 1, len(B)):
        if B[i] >= n:
            print("no")
            return
        if i >= n and B[i] == B[i - 1]:
            print("no")
            return

    print("yes")


T = int(input())
for _ in range(T):
    solve()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        List<Integer> A = new ArrayList<>();
        // 今天的沙堡
        for (int i = 1; i < n; ++i) {
            int j = sc.nextInt() - 1;
            A.add(j);
        }

        int m = sc.nextInt();
        List<Integer> B = new ArrayList<>();
        // 明天的沙堡
        for (int i = 1; i < m; ++i) {
            int j = sc.nextInt() - 1;
            B.add(j);
        }

        // 今天的沙堡数量必然小于等于明天的沙堡数量
        if (n > m) {
            System.out.println("no");
            return;
        }

        // 新增的沙堡的父亲沙堡编号全都是 < n 的，
        // 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）
        // 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻
        Collections.sort(B.subList(n - 1, B.size()));
        for (int i = n - 1; i < B.size(); ++i) {
            if (B.get(i) >= n) {
                System.out.println("no");
                return;
            }
            if (i >= n && B.get(i).equals(B.get(i - 1))) {
                System.out.println("no");
                return;
            }
        }

        System.out.println("yes");
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func solve(scanner *bufio.Scanner) {
	n := nextInt(scanner)
	A := make([]int, n-1)
	// 今天的沙堡
	for i := 0; i < n-1; i++ {
		A[i] = nextInt(scanner) - 1
	}

	m := nextInt(scanner)
	B := make([]int, m-1)
	// 明天的沙堡
	for i := 0; i < m-1; i++ {
		B[i] = nextInt(scanner) - 1
	}

	// 今天的沙堡数量必然小于等于明天的沙堡数量
	if n > m {
		fmt.Println("no")
		return
	}

	// 新增的沙堡的父亲沙堡编号全都是 < n 的，
	// 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）
	// 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻
	sort.Ints(B[n-1:])
	for i := n - 1; i < len(B); i++ {
		if B[i] >= n {
			fmt.Println("no")
			return
		}
		if i >= n && B[i] == B[i-1] {
			fmt.Println("no")
			return
		}
	}

	fmt.Println("yes")
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	return n
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	T := nextInt(scanner)
	for i := 0; i < T; i++ {
		solve(scanner)
	}
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    let T = parseInt(lines[0]);
    let index = 1;
    while (T--) {
        let n = parseInt(lines[index++]);
        let A = lines[index++].split(' ').map(x => parseInt(x));
        // 今天的沙堡
        for (let i = 0; i < n-1; ++i) {
            A[i] -= 1;
        }

        let m = parseInt(lines[index++]);
        let B = lines[index++].split(' ').map(x => parseInt(x));
        // 明天的沙堡
        for (let i = 0; i < m-1; ++i) {
            B[i] -= 1;
        }

        // 今天的沙堡数量必然小于等于明天的沙堡数量
        if (n > m) {
            console.log("no");
            continue;
        }

        let is_no = false; 

        // 新增的沙堡的父亲沙堡编号全都是 < n 的，
        // 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）
        // 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻
        B.slice(n - 1).sort((a, b) => a - b);
        for (let i = n - 1; i < B.length; ++i) {
            if (B[i] >= n) {
                console.log("no");
                is_no = true;
                break;
            }
            if (i >= n && B[i] === B[i - 1]) {
                console.log("no");
                is_no = true;
                break;
            }
        }
        if (!is_no) console.log("yes");
    }
});

题目描述

小美在海边建了一个沙堡乐园。

里面有一个巨大的沙堡，小美每年都会增加这个沙堡的层数，但也有一定的规律：

1、沙堡底层序号为 $1$ ；

2、沙堡的任何一个部分每年最多只能增加一个小沙堡(也可能不增加) ；

3、新建的小沙堡一定是独立的，没有和其他小沙堡连接(除了父亲沙堡)；

现在小美准备了今年沙堡的示意图和明年沙堡的设计图，他想让你告诉他，第一座沙堡明年能否变成第二座沙堡。

输入描述

输入第一行为 $T$ ，表示 $T$ 组数据。( $1≤T≤10$ )

对于每一组数据，包含4行：

第一行是第一座沙堡的个数：$n$ ，第二行有 $n-1$ 个数字 $l_i(i=2,3, \dots ,n)$ 表示第 $i$ 个沙堡的是建在第 $l_i(i=2,3, \dots ,n)$ 个沙堡上的。

第三行是第二座沙堡的个数：$m$ ，第四行有 $m-1$ 个数字 $r_i(i=2,3, \dots ,n)$ 表示第 $i$ 个沙堡是建在第 $r_i(i=2,3, \dots ,n)$个沙堡上的。

($1≤n,m≤50000,1≤l_i,r_i≤i$)

输入保证两座沙堡的对应序号相同，即两座沙堡的共有点的父节点相同，且第二座包括第一座的所有节点。

输出描述

如果第一座明年有可能建成第二座，输出“yes ”，否则输出”no”.

样例

样例输入

1
5
1 1 1 4
8
1 1 1 4 5 1 4

样例输出

yes