SOLVE

LATER

Party With Trees

Problem

Editorial

Analytics

Let me come straight to the question:

There are

ttest cases. For each test case -You are given a tree consisting of

nnodes labelled from1ton(each node has unique label), each node has valuenode[i]in it. Now, you are givenq1queries of the formu,v,kwhere it is guaranteed thatu is an ancestor of vand you are supposed to addkto the value of each node on the path fromutov(includinguandv). After answering all theq1queries, print the values of all the nodes in the order1tonon a single line.After that, you are given

q2queries of the typeu,vwhere it is guaranteed thatu is an ancestor of vand you need to print the sum of values of all nodes on the path fromutov(includinguandv).Print the answer to each of the

q2queries on a single line containingq2space separated integers.

NOTE:

Root of the tree is the node whose parent is 0. (0 is just a dummy value, and should not be considered as a node).Each node can have any number of children. But each node has exactly one parent (Except the root which has no parent).

Ancestor is a node reachable by repeated proceeding from child to parent. Thus root is the ancestor of all nodes.

IMPORTANT: Every node is also an ancestor of itself.

CONSTRAINTS:1<=t<=10

1<=n<=200000

1<=q1+q2<=2 * 10^6

q2>=1

0<=node[i]<=10^9

0<=k<=100000

1<=u,v<=n

INPUT:The first line contains a single integer

t, denoting the number of test cases.For each test case -

The first line contains a single integer

ndenoting the number of nodes in the tree.The next line contains

nspace separated integers denotingnode[i].The next line contains

nspace separated integers where theithintegerparent[i]is the parent of nodei.

For exactly one i, parent[i]=0. This means that node i is the root (SEE NOTE ABOVE).The next line contains a single integer

q1denoting the number of queries of the formu,v,kas described above.The next

q1lines contain exactly3space separated integersu,v,k.The next line contains a single integer

q2denoting the number of queries of the formu,vas described above.The next

q2lines contain exactly2space separated integersu,v.

OUTPUT:Each test case should consist of

2lines of output. For each test case -The first line should consist of

nspace separated integersnode[i]denoting the node values after answering all theq1queries of the typeu,v,k.The second line should consists of

q2space separated integers, theithinteger denotes the answer to theithquery of typeu,vas described above.

:Problem AuthorViral Mehta

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
512 MB

Source Limit:
2048 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"b321df2": "/pagelets/problems-hint/algorithm/party-with-trees/", "b321da7": "/pagelets/show-submission/algorithm/party-with-trees/", "b321dc6": "/pagelets/suggested-problems/algorithm/party-with-trees/", "b321e07": "/pagelets/recommended-problems/algorithm/party-with-trees/", "b321ddd": "/pagelets/problem-author-tester/algorithm/party-with-trees/"}

{}

realtime.hackerearth.com

80

be00c35e7d394d68601a645e2c7cdc1827103210

58a29e5cae2309f04b28

/realtime/pusher/auth/