{"problem":{"name":"Mex Game on Tree","description":{"content":"You are given a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i\\ (2\\leq i \\leq N)$ is $P_i$. Some vertices of the rooted tree have non-negative i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc162_c"},"statements":[{"statement_type":"Markdown","content":"You are given a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i\\ (2\\leq i \\leq N)$ is $P_i$.\nSome vertices of the rooted tree have non-negative integers from $0$ to $N$ written on them. This information is given by the sequence $A=(A_1,A_2,\\ldots,A_N)$. If $A_i \\neq -1$, vertex $i$ has the integer $A_i$ written on it; if $A_i=-1$, vertex $i$ does not have an integer written on it.\nAlice and Bob play a game. Alice goes first, and they take turns performing the following operation until all vertices have an integer written on them.\n\n*   Choose one vertex without an integer written on it and write a non-negative integer between $0$ and $N$ on it.\n\nAfter the operations, for each vertex $v$, let $f(v)$ be the smallest non-negative integer not written on any vertex (including $v$) in the subtree rooted at vertex $v$.\nIf there is a vertex $v$ such that $f(v) = K$, Alice wins. Otherwise, Bob wins. Determine the winner when both players play optimally.\nThere are $T$ test cases. Answer each of them.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^3$\n*   $2 \\leq N \\leq 10^3$\n*   $0 \\leq K \\leq N$\n*   $1 \\leq P_i < i\\ (2\\leq i\\leq N)$\n*   $-1 \\leq A_i \\leq N\\ (1\\leq i\\leq N)$\n*   All input values are integers.\n*   The sum of $N$ over all test cases in a single input is at most $2\\times 10^3$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$ $K$\n$P_2$ $P_3$ $\\ldots$ $P_N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc162_c","tags":[],"sample_group":[["2\n4 2\n1 1 2\n-1 -1 3 1\n6 4\n1 2 2 1 3\n-1 -1 -1 -1 -1 -1","Alice\nBob\n\nIn the first test case, if Alice writes $0$ on vertex $2$, then $f(2) = 2$ regardless of Bob's operation. Therefore, Alice can win.\nIn the second test case, Bob can ensure that there will be no vertex with $f(v) = 4$ by choosing the right integer to write."]],"created_at":"2026-03-03 11:01:13"}}