P15114 [CTT Paper 2026] Nowhere to Store

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.

**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$.

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$.

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