Lantern Path Updates Problem

Lantern Path Updates Problem — ExecCode Hard DSA Practice

Solve the Lantern Path Updates problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Problem Statement You have a tree with N lanterns. It is connected, so there are N−1 edges. Root is lantern 1. Each lantern has a brightness. There are Q operations: 1 U V — print the sum on the path from U to V (both ends included) 2 U V X — add X to every lantern on the path from U to V 3 U — print the sum of the subtree of U (including U) 4 U X — add X to every lantern in the subtree of U Lanterns are numbered from 1. X may be negative. Input Format An operation is one of: Output Format Print one line for each type-1 and type-3 operation. Type-2 and type-4 print nothing. Constraints Use 64-bit integers. Example 1 Input Path 1—2—3 starts as 1 + 5 + 3 = 9. Then add 1 on that same path. Ask the path sum again: 12. Output Example 2 Input One lantern. The path is itself. Output Example 3 Input Path sum is 4 + 9 = 13. The second operation adds 1 and prints nothing. Output

Examples

Input 3 3 1 5 3 1 2 2 3 1 1 3 2 1 3 1 1 1 3; Output 9 Input 1 1 7 1 1 1; Output 7. Input 2 2 4 9 1 2 1 1 2 2 1 2 1; Output 13

Constraints

1 ≤ N,Q ≤ 2000, |values|,|X| ≤ 1e9.

Practice Lantern Path Updates free on ExecCode. Browse DSA problems, topic map, and placement guides.