We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Heavy Light 2 White Falcon

Heavy Light 2 White Falcon

Problem
Submissions
Leaderboard
Discussions

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment.

You are given a tree with nodes and each node's value is initially .

Let's denote the path from node to node like this: , where and , and and are connected.

The problem asks you to operate the following two types of queries on the tree:

  • "1 u v x" Add to , to , to , ..., to .
  • "2 u v" print the sum of the nodes' values on the path between and at modulo .

Input Format

First line cosists of two integers and seperated by a space.
Following lines contains two integers which denote the undirectional edges of the tree.
Following lines contains one of the query types described above.

Note: Nodes are numbered by using 0-based indexing.

Constraints

Output Format

For every query of second type print a single integer.

Sample Input

3 2
0 1
1 2
1 0 2 1
2 1 2

Sample Output

5

Explanation

After the first type of query, . Hence the answer of the second query is .

Author

ikbalkazar

Difficulty

Hard

Max Score

100

Submitted By

1431

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy