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…, a n which is a permutation of 1, 2, …, n. Now, Mewoth makes q queries of one of the following forms:
- 1 l r v: meaning Bash should report
, where 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
The first line contains two integers n and q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) — 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, …, a n which is a permutation of 1, 2, …, 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 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 106). It is guaranteed that the given graph is a tree.
Each query consists of two lines. First line contains single integer t, indicating the type of the query. Next line contains the description of the query:
- t = 1: Second line contains three integers a, b and c (1 ≤ a, b, c < 230) using which l, r and v can be generated using the formula given below:
,
,
.
- t = 2: Second line contains single integer a (1 ≤ a < 230) using which x can be generated using the formula given below:
.
The ans i is the answer for the i-th query, assume that ans 0 = 0. If the i-th query is of type 2 then ans i = ans i - 1. It is guaranteed that:
- for each query of type 1: 1 ≤ l ≤ r ≤ n, 1 ≤ v ≤ n,
- for each query of type 2: 1 ≤ x ≤ n - 1.
The 
operation means bitwise exclusive OR.
Output
For each query of type 1, output a single integer in a separate line, denoting the answer to the query.
Example
input
5 5
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1
1 5 4
1
22 20 20
2
38
2
39
1
36 38 38
output
23
37
28
Note
In the sample, the actual queries are the following:
- 1 1 5 4
- 1 1 3 3
- 2 3
- 2 2
- 1 1 3 3
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 | #include <bits/stdc++.h>using namespace std;const long long inf = (long long) 1e18;const int N = 400010;vector < pair <int, long long> > forc[N];vector < pair <int, long long> > centroid[N];long long dist[N];long long last_dist[N];int sub[N];bool alive[N];vector < pair <int, int> > g[N];int perm[N], pos[N];int v_goes_to[N];vector <int> all;vector <int> in_forc[N];void dfs(int v, int pr) {all.push_back(v);sub[v] = 1;int sz = g[v].size();for (int j = 0; j < sz; j++) { int u = g[v][j].first; if (!alive[u] || u == pr) { continue; } int len = g[v][j].second; dist[u] = dist[v] + len; dfs(u, v); sub[v] += sub[u]; }}void build(int v) { all.clear(); dfs(v, -1); { // changing the root int old_v = v; int total = sub[v]; int pr = -1; while (true) { bool found = false; int sz = g[v].size(); for (int j = 0; j < sz; j++) { int u = g[v][j].first; if (!alive[u] || u == pr) { continue; } if (2 * sub[u] >= total) {pr = v;v = u;found = true;break;}}if (!found) {break;}}v_goes_to[old_v] = v;}all.clear();dist[v] = 0;dfs(v, -1);int cnt = all.size();for (int i = 0; i < cnt; i++) { int u = all[i]; centroid[u].push_back(make_pair(v, dist[u])); } for (int i = 0; i < cnt; i++) { int u = all[i]; forc[v].push_back(make_pair(pos[u], dist[u] - last_dist[u])); last_dist[u] = dist[u]; } sort(forc[v].begin(), forc[v].end()); for (int j = 1; j < cnt; j++) { forc[v][j].second += forc[v][j - 1].second; } for (int i = 0; i < cnt; i++) { int u = perm[forc[v][i].first]; in_forc[u].push_back(i); } vector <int> children;for (int i = 0; i < (int) g[v].size(); i++) { int u = g[v][i].first; if (alive[u]) { children.push_back(u); } } alive[v] = false; for (int i = 0; i < (int) children.size(); i++) { build(children[i]); }}int main() { int n, tt; scanf("%d %d", &n, &tt); for (int i = 0; i < n; i++) { scanf("%d", perm + i); perm[i]--; pos[perm[i]] = i; } for (int i = 0; i < n - 1; i++) { int x, y, z; scanf("%d %d %d", &x, &y, &z); x--; y--; g[x].push_back(make_pair(y, z)); g[y].push_back(make_pair(x, z)); } for (int i = 0; i < n; i++) { alive[i] = true; } build(0); int last = 0; while (tt--) { int com; scanf("%d", &com); if (com == 1) { int from, to, ver; scanf("%d %d %d", &from, &to, &ver); from ^= last; to ^= last; ver ^= last; from--; to--; ver--; long long ans = 0; long long prev_d = 0; for (pair <int, long long> p : centroid[ver]) {int v = p.first;long long d = p.second;long long sumd = 0;int cnt = 0;{int pf = lower_bound(forc[v].begin(), forc[v].end(), make_pair(from, -inf)) - forc[v].begin();int pt = lower_bound(forc[v].begin(), forc[v].end(), make_pair(to + 1, -inf)) - forc[v].begin();if (pf < pt) { sumd += forc[v][pt - 1].second; if (pf > 0) {sumd -= forc[v][pf - 1].second;}cnt += pt - pf;}}ans += sumd + cnt * (d - prev_d);prev_d = d;}printf("%I64d\n", ans);last = ans & ((1 << 30) - 1); } else { int x; scanf("%d", &x); x ^= last; x--; int v1 = perm[x]; int v2 = perm[x + 1]; int c1 = centroid[v1].size(); int c2 = centroid[v2].size(); int i1 = 0; int i2 = 0; long long prev_d2 = 0; while (i1 < c1 && i2 < c2 && centroid[v1][i1].first == centroid[v2][i2].first) { int v = centroid[v1][i1].first; long long d2 = centroid[v2][i2].second; { int at = in_forc[v1][i1]; forc[v][at].second = (at == 0 ? 0LL : forc[v][at - 1].second) + d2 - prev_d2; swap(in_forc[v1][i1], in_forc[v2][i2]); } prev_d2 = d2; i1++; i2++; } for (int rot = 0; rot < 2; rot++) { while (i1 < c1) { int v = centroid[v1][i1].first; { int at = in_forc[v1][i1]; forc[v][at].first = pos[v2]; } i1++; } swap(v1, v2); swap(c1, c2); swap(i1, i2); } swap(perm[x], perm[x + 1]); pos[perm[x]] = x; pos[perm[x + 1]] = x + 1; } } return 0;} |
