canbashsavetheday

Can Bash Save the Day?

Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.

Initially, Meowth gives Bash a weighted tree containing \(n\) nodes and a sequence \(a_1, a_2, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, n\). Now, Mewoth makes \(q\) queries of one of the following forms:

  • \(1\) \(l\) \(r\) \(v\): meaning Bash should report \(\displaystyle \sum_{i = l}^{r}{\textrm{dist}(a_i, v)}\), where \(\textrm{dist}(a, b)\) is the length of the shortest path from node \(a\) to node \(b\) in the given tree.
  • \(2\) \(x\): meaning Bash should swap \(a_x\) and \(a_{x + 1}\) in the given sequence. This new sequence is used for later queries.
Help Bash to answer the questions!

Input format

The first line contains two integers \(n\) and \(q\) \((1 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)\) — the number of nodes in the tree and the number of queries, respectively.

The next line contains \(n\) space-separated integers — the sequence \(a_1, a_2, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, n\).

Each of the next \(n - 1\) lines contain three space-separated integers \(u\), \(v\), and \(w\) denoting that there exists an undirected edge between node \(u\) and node \(v\) of weight \(w\), \((1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^6)\). It is guaranteed that the given graph is a tree.

Each query consists of one line. The first integer is \(t\), indicating the type of the query. Some integers follow:

  • t = 1: Three integers \(l\), \(r\) and \(v\) \((1 \leq l \leq r \leq n, 1 \leq v \leq n)\).
  • t = 2: A single integer \(x\) \((1 \leq x \leq n - 1)\).

Output format

For each query of type \(1\), output a single integer in a separate line, denoting the answer to the query.

Limits

Subtask # Score Constraints
1 8 \(n, q \leq 2000\)
2 15 \(l = 1\)
\(r = n\)
3 20 \(n, q \leq 50000\)
All queries are of type \(1\).
4 21 All queries are of type \(1\).
5 36 No additional constraints

Samples

Sample Input 1 Sample Output 1
5 5
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1 1 5 4
1 1 3 3
2 3
2 2
1 1 3 3
23
37
28



Submitting to 'canbashsavetheday'


You're not logged in! Click here to login


Submitting to 'canbashsavetheday'


You're not logged in! Click here to login


Submitting .cpp to 'canbashsavetheday'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 5 Seconds
Memory Limit: 1024MB
No. of ACs: 5
Your best score: 0
Source: Codeforces 757G

Subtask Score
1 8
2 15
3 20
4 21
5 36
6 0
7 0