6409：没有兄弟的舞会

题目描述

度度熊、光羽、带劲三个人是好朋友。

度度熊有一棵$n$个点的有根树，其中1号点为树根。除根节点之外，每个点都有父节点，记$i$号点的父节点为$fa[i]$。

度度熊称点$i$和点$j$是**兄弟**（其中$i \neq j$）当且仅当$fa[i]=fa[j]$。

第$i$个点的权值为$A_i$。现要求选出一个点集，该点集合法当且仅当**点集中至多只有一对兄弟**。

度度熊想知道，在所有可行的点集中，权值和**最大**以及**最小**的点集权值和分别是多少？

输入解释

第一行一个数，表示数据组数$T$。

每组数据第一行一个整数$n$；第二行$n-1$个数，表示$fa[2],fa[3],..,fa[n]$；第三行$n$个数，表示$A_i$。

数据组数T=100，满足：

- $1 \le n \le 10^5$
- $-10^9 \le A_i \le 10^9$
- $1 \le fa[i] < i$

其中90%的数据满足$n \le 1000$。

输出解释

每组数据输出一行，每行包含两个数，分别表示权值和的**最大值**和**最小值**。

输入样例

2
5
1 1 2 2 
-4 -4 -1 -2 -5 
5
1 1 3 2 
-1 -4 2 0 -2

输出样例

0 -15
2 -7

来自杭电HDUOJ的附加信息

Recommend

chendu

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2018“百度之星”程序设计大赛 - 复赛

源链接： HDU-6409

最后修改于 2020-10-25T23:31:05+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	65536/65536K(Java/Others)