C. Alien Attack (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of Alien Attack. The only differences between this and the hard version are the constraints on the value of $$$n$$$ and $$$q$$$.

Westin is in a country with $$$n$$$ cities and $$$n-1$$$ bidirectional roads. The road network forms a tree. Cities are numbered from $$$1$$$ to $$$n$$$.

Each city $$$v$$$ has a power value $$$p_v(t)$$$ that depends on time $$$t$$$. Initially, at time $$$t=0$$$, every city has power $$$0$$$.

During an alien invasion, meteors may crash into some cities. It is guaranteed that each city is targeted by at most one meteor in total.

If a meteor crashes into city $$$x$$$ at time $$$t_0$$$ with initial energy $$$\textit{val}$$$, then for any time $$$t \ge t_0$$$, the power contributed by that meteor at city $$$x$$$ is:

$$$p_x(t) = \textit{val} - (t - t_0)$$$.

This value can be negative (the meteor keeps losing $$$1$$$ energy per second even after reaching $$$0$$$). Cities that have never been hit by a meteor have power $$$0$$$ at all times.

You are given $$$q$$$ queries of two types:

  • Type 1: $$$1\ t\ x\ val$$$ — a meteor crashes into city $$$x$$$ at time $$$t$$$ with initial energy $$$val$$$. It is guaranteed that city $$$x$$$ has not been targeted before.
  • Type 2: $$$2\ t\ a\ b$$$ — at time $$$t$$$, Westin's friend travels from city $$$a$$$ to city $$$b$$$.

For each type 2 query, output the total power on the simple path from $$$a$$$ to $$$b$$$ at exactly time $$$t$$$:

$$$$$$\sum_{v \in \text{path}(a,b)} p_v(t).$$$$$$
Note that this sum may be negative.
Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting a road between cities $$$u$$$ and $$$v$$$.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 5000$$$).

Each of the next $$$q$$$ lines describes a query in one of the following forms:

  • $$$1, t, x, val$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le x \le n$$$, $$$-10^9 \le \textit{val} \le 10^9$$$),
  • $$$2, t, a, b$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le a,b \le n$$$).

If at a time t there are both type 1 and type 2 queries, process the type 1 queries first. It is guaranteed that each city appears in at most one type 1 query.

Output

For each type 2 query, output a single integer — the total power on the path from $$$a$$$ to $$$b$$$ at time $$$t$$$.

Example
Input
3
1 2
2 3
4
1 1 2 5
2 2 1 3
2 4 1 3
2 4 2 2
Output
4
2
2
Note

Initially, all cities have power $$$0$$$.

Query 1: $$$1\ 1\ 2\ 5$$$

A meteor hits city $$$2$$$ at time $$$t_0=1$$$ with initial energy $$$5$$$. So for $$$t \ge 1$$$,

$$$p_2(t)=5-(t-1)=6-t.$$$

Query 2: $$$2\ 2\ 1\ 3$$$

At time $$$t=2$$$,

$$$p_2(2)=5-(2-1)=4.$$$
Cities $$$1$$$ and $$$3$$$ still have power $$$0$$$.

Path $$$1 \to 3$$$ is $$$(1,2,3)$$$, so the total is

$$$0+4+0=4.$$$

Query 3: $$$2\ 4\ 1\ 3$$$

At time $$$t=4$$$,

$$$p_2(4)=5-(4-1)=2.$$$
Thus the path sum on $$$1 \to 3$$$ is
$$$0+2+0=2.$$$

Query 4: $$$2\ 4\ 2\ 2$$$

The path from $$$2$$$ to $$$2$$$ contains only city $$$2$$$, so the answer is

$$$p_2(4)=2.$$$

Therefore the outputs are:

$$$4, 2, 2.$$$