#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0A

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0A

Repovive

Peak Average Subtree - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG0A. Peak Average Subtree

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given an N-ary tree with $N$ nodes rooted at node $0$ , where each node has an integer value, find the node whose subtree (including itself) has the maximum average value.

If there are ties, return the node with the smallest index.

The subtree of a node includes the node itself and all of its descendants.

To avoid floating-point issues, compare averages using cross-multiplication: compare $\text{sum}_1 \times \text{count}_2$ against $\text{sum}_2 \times \text{count}_1$ .

Constraints

$1 \le N \le 10^5$
$-10^4 \le \text{value}[i] \le 10^4$
The tree is given as a parent array: $\text{parent}[i]$ for $i = 1, 2, \ldots, N-1$ where $0 \le \text{parent}[i] < i$

Input

\begin{array}{l} N \\ v_0 \quad v_1 \quad \cdots \quad v_{N-1} \\ p_1 \quad p_2 \quad \cdots \quad p_{N-1} \end{array}

Output

$ans$

Samples

Input

4
1 5 2 1
0 0 1

Explanation

Subtree averages: Node 0: $(1+5+2+1)/4 = 9/4 = 2.25$ . Node 1: $(5+1)/2 = 3.0$ . Node 2: $2/1 = 2.0$ . Node 3: $1/1 = 1.0$ . Node 1 has the maximum average of 3.0. Answer: 1.

Output

Input

1
7

Explanation

Only one node (node 0) with value $7$ . Its subtree average is $7/1 = 7.0$ . Answer: 0.

Output

Input

3
5 5 5
0 0

Explanation

Subtree averages: Node 0: $(5+5+5)/3 = 5.0$ . Node 1: $5/1 = 5.0$ . Node 2: $5/1 = 5.0$ . All averages are equal. Tie-break by smallest index. Answer: 0.

Output

Given an N-ary tree with $N$ nodes rooted at node $0$ , where each node has an integer value, find the node whose subtree (including itself) has the maximum average value.

If there are ties, return the node with the smallest index.

The subtree of a node includes the node itself and all of its descendants.

To avoid floating-point issues, compare averages using cross-multiplication: compare $\text{sum}_1 \times \text{count}_2$ against $\text{sum}_2 \times \text{count}_1$ .

Constraints

$1 \le N \le 10^5$
$-10^4 \le \text{value}[i] \le 10^4$
The tree is given as a parent array: $\text{parent}[i]$ for $i = 1, 2, \ldots, N-1$ where $0 \le \text{parent}[i] < i$

\begin{array}{l} N \\ v_0 \quad v_1 \quad \cdots \quad v_{N-1} \\ p_1 \quad p_2 \quad \cdots \quad p_{N-1} \end{array}

$ans$

Subtree averages: Node 0: $(1+5+2+1)/4 = 9/4 = 2.25$ . Node 1: $(5+1)/2 = 3.0$ . Node 2: $2/1 = 2.0$ . Node 3: $1/1 = 1.0$ . Node 1 has the maximum average of 3.0. Answer: 1.

Only one node (node 0) with value $7$ . Its subtree average is $7/1 = 7.0$ . Answer: 0.

Subtree averages: Node 0: $(5+5+5)/3 = 5.0$ . Node 1: $5/1 = 5.0$ . Node 2: $5/1 = 5.0$ . All averages are equal. Tie-break by smallest index. Answer: 0.