#P10887. [2015yali备战noi]union

    ID: 10030 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600博弈论树形DP贪心图论数据结构递归动态规划

[2015yali备战noi]union

题目描述

有 NN 座城市,由 N−1N-1 条道路相连。任意两座城市之间恰有一条路径。初始时每座城市是一个独立的州。

合并分若干轮进行。每轮中,一个州至多和另一个州合并。两个州可以合并,当且仅当有一条道路的两端分别属于这两个州。合并得到的新州包含原先两个州的所有城市。

求将全部城市合并为一个州的最少轮数。

输入格式

第一行一个整数 tt(t≤30t\le 30),表示数据组数。每组两行:

  • 第一行一个整数 NN(2≤N≤6002\le N\le 600),城市编号为 0,1,…,N−10,1,\ldots,N-1。
  • 第二行 N−1N-1 个整数。第 ii 个整数 pp(1≤i≤N−11\le i\le N-1)表示城市 pp 与城市 ii 之间有一条道路。

输出格式

每组数据输出一行一个整数,表示最少合并轮数。

样例

3
4
0 1 2
8
0 1 2 0 0 3 3
9
0 1 1 1 1 0 2 2
2
4
5

原 PDF 题面