解题思路

工位之间虽然连成一棵树，但一次操作可以交换任意两个工位上的工牌，因此走廊结构并不影响答案。问题等价于：给定 $1$ 到 $n$ 的一个排列 $a$ ，通过交换把 $a$ 变成恒等排列，求最少交换次数。

将一个元素直接换到它应该在的位置上：若位置 $i$ 上的工牌编号为 $t$ 且 $t\neq i$ ，则把位置 $i$ 与位置 $t$ 上的工牌交换，这样编号 $t$ 就回到了工位 $t$ 。从 $n$ 到 $1$ 依次处理，每个位置不断执行上述交换，直到该位置已经放对。

每次交换都会让至少一个工牌回到正确工位，总次数等于 $n$ 减去排列中的环个数。

复杂度分析

实验室有 $n$ 个工位，编号为 $1$ 到 $n$ 。工位之间用 $n-1$ 条走廊相连，整体构成一棵树。每个工位上放着一张工牌，第 $i$ 个工位上的工牌编号为 $a_i$ 。这 $n$ 张工牌恰好构成 $1$ 到 $n$ 的一个排列。

一次操作可以任选两个工位，交换它们上面的工牌。目标是让第 $i$ 个工位上的工牌编号恰好等于 $i$ 。保证一定有解。

请计算最少需要多少次交换。

工位个数满足 $2 \le n \le 1000$ ，工牌编号与走廊两端点均在 $1$ 到 $n$ 之间。