题解

这题分析后发现，其实和树形结构无关，交换可以看成是，将节点的权值放到数组上，对数组进行交换。 由于题目说了是个排列，我们只要从前往后，碰到能交换的进行交换就可以了。

AC代码

• Python

n = int(input())

题意

给定一棵树，每个节点有一个权值。现在每次可以交换任意两个节点的权值，请问最少需要多少次交换可以使得每个节点的权值等于它的编号？保证给出的权值是一个排列，也就是说保证一定有解。

输入描述

第一行输入一个正整数 $n$，代表树上的节点数量。

第二行输入 $n$ 个正整数 $a_1, a_2, ..., a_n$，第 $i$ 个数字表示节点 $i$ 的权值，这 $n$ 个数互不相同。

接下来的 $n - 1$ 行，每行输入两个正整数 $u$ 和 $v$，代表节点 $u$ 和节点 $v$ 有一条边相连。

$2 \leq n \leq 1000$

$1 \leq u, v, a_i \leq n$

输出描述

一个整数，代表最小的交换次数。

示例1：

输入：

4
2 1 4 3
1 2
2 3
2 4

输出：

2