There are $$$n$$$ cities in Dadorlandtiria, numbered from $$$0$$$ to $$$n-1$$$. The country is connected with $$$n-1$$$ roads, where the $$$i$$$-th road connects cities $$$u[i]$$$ and $$$v[i]$$$. It costs $$$w[i]$$$ dadorian dollars to cross the $$$i$$$-th road. Each pair of cities is reachable from each other using these roads.
A company called "Work Alone" has to finish $$$q$$$ projects. Let's say for some project, $$$m$$$ workers are involved in it, where $$$m$$$ is an even number. The $$$i$$$-th worker lives in the $$$t[i]$$$-th city. For some reason, the CEO of "Work Alone" decided it would be better for workers to work in pairs, so workers should form $$$\frac{m}{2}$$$ pairs and meet in some city. You want to minimize the total cost workers have to pay for transportation.
Find the answer for each project independently.
The first line contains $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$).
The next $$$n-1$$$ lines contain $$$u[i]$$$, $$$v[i]$$$, and $$$w[i]$$$ ($$$0 \le u[i] \lt v[i] \le n - 1$$$, $$$q \le w[i] \le 10^9$$$).
The next $$$q$$$ lines contain $$$m$$$, followed by $$$m$$$ integers $$$t[0], t[1], \ldots, t[m-1]$$$ in the same line ($$$2 \le m \le 5 \cdot 10^5, 0 \le t[i] \le n-1$$$, all values of $$$t$$$ are distinct).
It is guaranteed that the total sum of $$$m$$$ among all projects does not exceed $$$5 \cdot 10^5$$$.
For each project query, print the minimum total cost of transportation.
| Group | Add. constraints | Points |
| $$$0$$$ | examples | $$$0$$$ |
| $$$1$$$ | $$$u[i]=i$$$ and $$$v[i]=i+1$$$ | $$$5$$$ |
| $$$2$$$ | $$$m \le 6, q \le 5 \cdot 10^4$$$ | $$$11$$$ |
| $$$3$$$ | $$$n \le 100$$$ | $$$15$$$ |
| $$$4$$$ | $$$n \le 1000$$$ | $$$15$$$ |
| $$$5$$$ | $$$q = 1, m = n$$$ | $$$21$$$ |
| $$$6$$$ | — | $$$33$$$ |
8 2 4 5 2 2 5 3 2 7 1 3 5 1 0 6 4 1 5 2 1 6 3 4 1 4 0 7 2 4 5
13 2
Dadorlandtiria In the first project, $$$m=4$$$ and $$$t=[1, 4, 0, 7]$$$.
- The first pair can be $$$(7, 4)$$$. If they meet at the $$$5$$$-th city, they spend $$$4+2=6$$$ dadorian dollars to reach city $$$5$$$.
- The second pair is $$$(1, 0)$$$. They can meet at the $$$6$$$-th city, spending $$$3+4=7$$$ dadorian dollars.
In the second project, $$$m=2$$$ and $$$t=[4, 5]$$$. $$$(4, 5)$$$ is the only pair, and they can meet at the $$$5$$$-th city for a total of $$$2+0=2$$$ dadorian dollars.
There are $$$2 \cdot n$$$ teams in the Soccer League. Teams are numbered from $$$0$$$ to $$$2 \cdot n - 1$$$.
Before the last round, the $$$i$$$-th team has $$$p[i]$$$ points. There will be $$$n$$$ games in the last round, where teams $$$a[i]$$$ and $$$b[i]$$$ will play against each other.
Each team wonders about the best final place their team can get. This is your task to calculate these values.
The team's final place equals the number of teams with strictly more points than their team $$$+ 1$$$. Teams with same points get the same place.
The winner of the game gets $$$3$$$ points, whereas the loser gets $$$0$$$ points. If the game ends in a draw, both teams get $$$1$$$ point each.
First line contains an integer $$$n$$$ – the number of games. ($$$1 \le n \le 10^5$$$)
Second line contains $$$2 \cdot n$$$ integers – $$$p[0], p[1], \ldots, p[2 \cdot n - 1]$$$. ($$$0 \le p[i] \le 5 \cdot 10^5$$$)
Next $$$n$$$ lines contain $$$a[i]$$$ and $$$b[i]$$$. ($$$0 \le a[i], b[i] \le 2 \cdot n - 1$$$)
It is guaranteed that each number from $$$0$$$ to $$$2 \cdot n - 1$$$ occurs exactly once among arrays $$$a$$$ and $$$b$$$.
In the single line print $$$2 \cdot n$$$ space-separated integers $$$t[0], t[1], \ldots, t[2 \cdot n - 1]$$$. Here, $$$t[i]$$$ must equal the best final place $$$i$$$-th team can get.
| Group | Add. constraints | Points |
| $$$0$$$ | examples | $$$0$$$ |
| $$$1$$$ | $$$n \le 2$$$ | $$$6$$$ |
| $$$2$$$ | $$$n \le 12$$$ | $$$11$$$ |
| $$$3$$$ | $$$n \le 200$$$ | $$$17$$$ |
| $$$4$$$ | $$$n \le 2000$$$ | $$$20$$$ |
| $$$5$$$ | — | $$$46$$$ |
2 47 45 50 48 0 2 3 1
1 2 1 1
Here, $$$p = [47, 45, 50, 48]$$$ and team $$$0$$$ will play against $$$2$$$, whereas team $$$3$$$ will play against $$$1$$$. Let's calculate the best place team $$$0$$$ can get:
- team $$$0$$$ should win team $$$2$$$. Team $$$0$$$ now has $$$47+3=50$$$ points and team $$$2$$$ has $$$50$$$ points too.
- the game between teams $$$3$$$ and $$$1$$$ should end in a draw. Team $$$3$$$ now has $$$48+1=49$$$ points and team $$$1$$$ has $$$45+1=46$$$ points.
In another scenario, team $$$3$$$ can get first place, so $$$t[3] = 1$$$. However, team $$$1$$$ can only get second place in their best scenario, so $$$t[1]$$$ should be $$$2$$$.
In the geometry class, Ulugbek learned about the triangle inequality. For three sticks of length $$$x$$$, $$$y$$$, and $$$z$$$ meters, the following properties should be held: $$$x+y \gt z$$$, $$$x+z \gt y$$$, and $$$y+z \gt x$$$. The perimeter of this triangle equals $$$x+y+z$$$ meters.
There are $$$n$$$ sticks of length $$$a[0], a[1], \ldots, a[n-1]$$$ meters. Ulugbek gives you $$$q$$$ queries of two types:
- $$$0 \; p \; v$$$ — set $$$a[p] := v$$$
- $$$1 \; l \; r$$$ — find the triangle with the largest perimeter if you can only use sticks in the range $$$[l, r]$$$, i.e. $$$a[l], a[l + 1], \ldots, a[r]$$$. Each side of the triangle must be created using exactly one stick. Return $$$0$$$ if you can't make any triangles.
The first line contains $$$n$$$ and $$$q$$$. ($$$1 \le n, q \le 2 \cdot 10^5$$$)
The second line contains $$$a[0], a[1], \ldots, a[n-1]$$$. ($$$1 \le a[i] \le 5 \cdot 10^8$$$).
The next $$$q$$$ lines contain queries of either type $$$0 \; p \; v$$$ or $$$1 \; l \; r$$$. ($$$0 \le p \le n - 1$$$, $$$1 \le v \le 5 \cdot 10^8$$$), ($$$0 \le l \le r \le n - 1$$$).
For each query of type $$$1 \; l \; r$$$, print the largest possible perimeter using sticks in the range $$$[l, r]$$$, or print $$$0$$$ if it is impossible to create a triangle.
| Group | Add. constraints | Points |
| $$$0$$$ | examples | $$$0$$$ |
| $$$1$$$ | $$$n, q \le 80$$$ | $$$3$$$ |
| $$$2$$$ | $$$n, q \le 400$$$ | $$$7$$$ |
| $$$3$$$ | $$$n, q \le 3000$$$ | $$$16$$$ |
| $$$4$$$ | All values of $$$a[i]$$$ and $$$v$$$ are integer powers of $$$2$$$. | $$$15$$$ |
| $$$5$$$ | There are no queries of type $$$0 \; p \; v$$$ | $$$16$$$ |
| $$$6$$$ | $$$a[i], v \le 10^5$$$ | $$$20$$$ |
| $$$7$$$ | $$$n \le 5 \cdot 10^4$$$ | $$$10$$$ |
| $$$8$$$ | — | $$$13$$$ |
7 3 3 1 4 1 5 9 2 1 2 6 0 0 7 1 0 2
11 0
For query $$$l=2$$$ and $$$r=6$$$, we can use sticks $$$a[2] = 4$$$, $$$a[4] = 5$$$, and $$$a[6] = 2$$$. The perimeter equals $$$4+5+2=11$$$.
Then, we are asked to set $$$a[0] := 7$$$. Now, $$$a=[7, 1, 4, 1, 5, 9, 2]$$$.
In the next query, $$$l=0$$$ and $$$r=2$$$. The only triplet is $$$(7, 1, 4)$$$, which doesn't follow the triangle inequality. Thus, the answer is $$$0$$$.