{"problem":{"name":"Get the Salary of Atcoder","description":{"content":"There are $N$ workers in Atcoder company. Each worker is numbered $0$ through $N - 1$, and the boss for worker $i$ is $p_i$ like a tree structure and the salary is currently $a_i$. ($p_i < i$, especia","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"s8pc_4_g"},"statements":[{"statement_type":"Markdown","content":"There are $N$ workers in Atcoder company. Each worker is numbered $0$ through $N - 1$, and the boss for worker $i$ is $p_i$ like a tree structure and the salary is currently $a_i$. ($p_i < i$, especially $p_0 = -1$ because worker $0$ is a president)  \nIn atcoder, the boss of boss of boss of ... (repeated $k$ times) worker $i$ called \"$k$\\-th upper boss\", and \"$k$\\-th lower subordinate\" called for vice versa.  \n  \nYou have to process $Q$ queries for Atcoder:  \n\n*   Query 1: You are given $v_i, d_i, x_i$. Increase the salary of worker $v_i$, and all $j$\\-th ($1 ≤ j ≤ d_i$) lower subordinates by $x_i$.\n*   Query 2: You are given $v_i, d_i$. Calculate the sum of salary of worker $v_i$ and all $j$\\-th ($1 ≤ j ≤ d_i$) lower subordinates.\n*   Query 3: You are given $pr_i, ar_i$. Now Atcoder has a new worker $c$! ($c$ is the current number of workers) The boss is $pr_i$, and the first salary is $ar_i$.\n\nProcess all queries!!!\n\n## Input Format\n\nLet the $i$\\-th query $query_i$, the input format is following:  \n\n$N$ $Q$\n$p_0$ $a_0$\n$p_1$ $a_1$\n :   :\n$p_{N - 1}$ $a_{N - 1}$\n$query_0$\n$query_1$\n :   :\n$query_{Q - 1}$\n\nTHe format of $query_i$ is one of the three format:  \n\n1 $v_i$ $d_i$ $x_i$\n\n2 $v_i$ $d_i$\n\n3 $pr_i$ $ar_i$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"s8pc_4_g","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:14"}}