Query On Tree

发布时间: 2018年9月12日 20:20   最后更新: 2018年9月12日 22:21   时间限制: 2000ms   内存限制: 256M

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

Let's denote the path from node $u$ to node $v$ like this: $p_1,p_2,p_3,\cdots,p_k$, where $p_1 = u$ and $p_k = v$, and $p_i$ and $p_{i + i}$ are connected.

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

  • "1 u v x" Add $x$ to $val_{p1}$ ,$2x$ to $val_{p2}$ , $3x$ to $val_{p3}$, ..., $kx$ to $val_{pk}$.
  • "2 u v" print the sum of the nodes' values on the path between $u$ and $v$ at modulo $10 ^ 9 + 7$.

First line cosists of two integers $N$ and $Q$ seperated by a space.
Following $N - 1$ lines contains two integers which denote the undirectional edges of the tree.
Following $Q$ lines contains one of the query types described above.
Note: Nodes are numbered by using 0-based indexing.
Constraints
$1 \le N, Q \le 50000$
$0 \le x < 10 ^ 9 + 7$

For every query of second type print a single integer.

复制
3 2
0 1
1 2
1 0 2 1
2 1 2
5

After the first type of query, $val_0 = 1$, $val_1 = 2$, $val_2 = 3$. Hence the answer of the second query is $2 + 3 = 5$.

data structure

HackerRank