Problem Description

You are given a tree with $n$ nodes rooted at $1$, and $n$ triples $(a_i,b_i,c_i)$.

For every $s\in[1,k]$, you need to find a non-negative integer sequence $h$ of length $n$ such that:

• $\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)$, where $\mathrm{son}(i)$ denotes the set of children of node $i$, and $g_j$ denotes the sum of $h$ within the subtree of $j$.

And you should minimize $\sum_{i=1}^nf(a_i,b_i,c_i,h_i)$, where $f(a,b,c,x)=ax^2+bx+c$.

Given $op\in\{0,1\}$, if $op=0$, you need to output the answers for $s=1,2,...,k$; if $op=1$, you need to output the answer for $s=k$ and construct any one optimal solution.

Input Format

This problem contains multiple test cases.

The first line contains three numbers $id,op,T$, representing the subtask ID, whether you are required to output a solution for $s=k$, and the number of test cases.

Then for each test case:

The first line contains two numbers $n,k$.

The second line contains $n-1$ numbers $p_2,p_3,...,p_n$, where $p_i$ denotes the parent of node $i$.

The next $n$ lines each contain three numbers; the three numbers on the $i$-th line are $a_i,b_i,c_i$.

Output Format

If $op=0$, then for each test case, output one line with $k$ numbers, where the $i$-th number is the answer for $s=i$.

If $op=1$, then for each test case, first output one line with one number, the answer when $s=k$, and then output one line with $n$ numbers, where the $i$-th number is $h_i$, describing an optimal solution when $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 

Hint

For $100\%$ of the data, $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$. Note that there is no guarantee on the range of $\sum k$.

A randomly generated tree shape means that $p_i$ is generated uniformly at random from $[1,i-1]$.

For subtasks with $op=0$, the time limit is $3$ s.

For subtasks with $op=1$, the time limit is $8$ s.

Translated by ChatGPT 5