Tree Query

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME79/hindi/TREEQ1.pdf),[Bengali](http://www.codechef.com/download/translated/LTIME79/bengali/TREEQ1.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME79/mandarin/TREEQ1.pdf), [Russian](http://www.codechef.com/download/translated/LTIME79/russian/TREEQ1.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME79/vietnamese/TREEQ1.pdf) as well. You are given a tree with $N$ vertices (numbered $1$ through $N$); vertex $1$ is the root. Initially, for each valid $i$, the $i$th vertex has a weight $w_i$. You should perform a sequence of $Q$ operations of the following two types: 1. Add $x$ to the weight of vertex $v$. 2. Add $x$ to the weight of each vertex in the subtree of vertex $v$ (including $v$). Let's define a function $f(u) = \sum_{i=1}^N w_i \cdot d(i, u)$, where $d(i, u)$ denotes the distance between vertices $i$ and $u$. After each operation, find an integer $u$ such that $f(u)$ is minimum amoung $f(1), f(2), \ldots, f(N)$, if there are multiple values of $u$ find smallest one. ### Input  The first line of the input contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $w_1, w_2, \ldots, w_N$.  $N1$ lines follow. Each of these lines contains two spaceseparated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.  Each of the next $Q$ lines contains three spaceseparated integers $t$, $v$ and $x$ describing one operation, where $t$ denotes the type of the operation. ### Output Print $Q$ lines. For each valid $i$, the $i$th of these lines should contain one integer $u$ such that $f(u)$ is minimum among $f(1), f(2), \ldots, f(N)$ after the $i$th operation, if there are multiple values of $u$ find smallest one. ### Constraints  $1 \le N, Q \le 10^5$  $1 \le w_i \le 10^7$ for each valid $i$  $x \le 10^7$  the weights of all vertices remain positive after each operation ### Subtasks **Subtask #1 (50 points):** $N, Q \le 10^3$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 5 2 5 5 5 5 10 1 2 2 3 3 4 3 5 1 5 5 2 4 50 ``` ### Example Output ``` 3 4 ```Author:  chemthan 
Tags  chemthan 
Date Added:  25122019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 