Background

This problem comes from the original BZOJ. We acknowledge that the statement and original testdata are copyrighted by the original BZOJ or the problem author who authorized BZOJ to use it. If you are the copyright holder and believe we have infringed your rights, please contact us.

Shuoshou really likes climbing trees, which scares the Pipishu (pípíshǔ) on the tree.

You are given a tree with $n$ nodes, where all edge weights are $1$. Initially, there are no Pipishu on the tree.

Each time, Shuoshou jumps to a node $u$ and attracts $w$ Pipishu to each node whose distance to him is at most $d$. Since the Pipishu are attracted by Shuoshou, they will stay at their nodes and never move.

Shuoshou is curious: at the current moment, how many of his good friends—Pipishu—are on node $u$.

Problem Description

The background can be abstracted into the following problem:

Given a tree with $n$ nodes, where all edge weights are $1$, and the initial node weights are all $0$. Perform $m$ operations:

• $\text{Q x}$: query the node weight of node $x$.
• $\text{M x d w}$: add $w$ to the node weight of every node whose distance to node $x$ is at most $d$.

Input Format

The first line contains two positive integers $n, m$.

The next $n - 1$ lines each contain two positive integers $u, v$, indicating that there is an edge between $u$ and $v$.

The next $m$ lines each describe one of the two operations above.

Output Format

For each $Q$ operation, output the current node weight of node $x$.

7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2

2
3
6

Hint

For all data, it is guaranteed that $1 \leq n, m \leq 10^5$ and $|w| \leq 10^4$. Note that $w$ is not necessarily positive.

Translated by ChatGPT 5