题目描述

给定一棵 $n$ 个点以 $1$ 为根的树和 $n$ 个三元组 $(a_i,b_i,c_i)$。

$\forall s\in[1,k]$，你需要求一个长度为 $n$ 的非负整数序列 $h$，满足：

• $\forall i\in[1,n],h_i\in[0,k]$。
• $\sum_{i=1}^nh_i=s$。
• $\forall i\in[1,n],(h_i\bmod 2)\ge\sum_{j\in\mathrm{son(i)}}(g_j\bmod 2)$，其中 $\mathrm{son}(i)$ 表示点 $i$ 的儿子集合，$g_j$ 表示 $j$ 子树内 $h$ 的和。

并最小化 $\sum_{i=1}^nf(a_i,b_i,c_i,h_i)$ 的值，其中 $f(a,b,c,x)=ax^2+bx+c$。

给定 $op\in\{0,1\}$，若 $op=0$，则请求出 $s=1,2,...,k$ 的答案；若 $op=1$，则请求出 $s=k$ 的答案并构造任意一种最优方案。

输入格式

本题包含多组测试数据。

第一行三个数 $id,op,T$，分别表示子任务编号、是否要求输出 $s=k$ 的方案和测试组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行两个数 $n,k$。

第二行 $n-1$ 个数 $p_2,p_3,...,p_n$，$p_i$ 表示 $i$ 号点的父亲。

接下来 $n$ 行，每行三个数，第 $i$ 行的三个数分别表示 $a_i,b_i,c_i$。

输出格式

若 $op=0$，则对于每组测试数据，输出一行 $k$ 个数，第 $i$ 个数表示 $s=i$ 的答案。

若 $op=1$，则对于每组测试数据，先输出一行一个数表示 $s=k$ 时的答案，再输出一行 $n$ 个数，第 $i$ 个数表示 $h_i$，描述 $s=k$ 时的一种最优方案。

0 0 1
5 5
1 1 2 2
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0

1 2 3 4 7 

0 1 1
5 5
1 1 2 2
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0

7
1 1 2 0 1 

提示

对于 $100\%$ 的数据，$1\le T,\sum n\le 3\times 10^4,1\le k\le 2\times 10^3,0\le a_i,|b_i|,|c_i|\le 10^6,1\le p_i<i$，注意没有保证 $\sum k$ 的范围。

子任务编号	$\sum n\le$	$k\le$	$op=$	特殊性质	空间限制	分值
$1$	$10$	$5$	$0$	无	$512$ MB	$5$
$2$	$300$	$200$
$3$	$2\times 10^4$	$1.5\times 10^3$				$15$
$4$			$1$			$10$
$5$			$0$	树的形态随机生成	$32$ MB	$5$
$6$			$1$
$7$				树的形态是一条链		$15$
$8$			$0$	无		$10$
$9$			$1$
$10$	$3\times 10^4$	$2\times 10^3$	$0$
$11$			$1$

树的形态随机生成是指，$p_i$ 在 $[1,i-1]$ 之间随机生成。

对于 $op=0$ 的子任务，时间限制为 $3$ s。

对于 $op=1$ 的子任务，时间限制为 $8$ s。