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
| #include <bits/stdc++.h> #define maxn 100005 using namespace std; typedef pair<int, int> pii; vector<pii> G[maxn]; struct query { int first, second, id; }; struct edge { int w, id; }; vector<query> qs; vector<pii> ans; int n, q, len, t, tt, bl; int el[maxn], er[maxn]; edge L[2 * maxn], R[2 * maxn]; bool vis[maxn]; int cnt[maxn], cnt_block[maxn]; void dfs(int u, int fa, int id, int ww) { el[u] = ++t; for (auto e : G[u]) { int v = e.first, w = e.second; if (v == fa) continue; R[t] = edge{w, ++tt}; L[t + 1] = edge{w, tt}; dfs(v, u, tt, w); } R[t] = edge{ww, id}; er[u] = ++t; L[t] = edge{ww, id}; } void add(int a) { cnt[a]++; if (cnt[a] == 1) cnt_block[a / bl]++; } void del(int a) { cnt[a]--; if (cnt[a] == 0) cnt_block[a / bl]--; }
inline bool cmp(const query& a, const query& b) { if (a.first / len != b.first / len) return a.first / len < b.first / len; return a.second < b.second; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> q; len = 2 * n / sqrt(q); bl = sqrt(maxn); int u, v, w; for (int i = 1; i < n; i++) { cin >> u >> v >> w; w = min(w, n); G[u].push_back(pii(v, w)); G[v].push_back(pii(u, w)); vis[i] = false; } dfs(1, 0, 0, 100005); for (int i = 1; i <= q; i++) { cin >> u >> v; int a = el[u], b = el[v]; if (a > b) {int tmp = a; a = b; b = tmp;} qs.push_back(query{a, b, i}); } sort(qs.begin(), qs.end(), cmp); int l = 1, r = 1; for (auto p : qs) { int &ql = p.first, &qr = p.second; while (l > ql) { if (!vis[L[l].id]) { add(L[l].w); } else { del(L[l].w); } vis[L[l].id] = !vis[L[l].id]; l--; } while (r < qr) { if (!vis[R[r].id]) { add(R[r].w); } else { del(R[r].w); } vis[R[r].id] = !vis[R[r].id]; r++; } while (l < ql) { if (!vis[R[l].id]) { add(R[l].w); } else { del(R[l].w); } vis[R[l].id] = !vis[R[l].id]; l++; } while (r > qr) { if (!vis[L[r].id]) { add(L[r].w); } else { del(L[r].w); } vis[L[r].id] = !vis[L[r].id]; r--; } int i, j; for (i = 0; i <= 100000 / bl; i++) { if (cnt_block[i] != bl) break; } for (j = i * bl; j < (i + 1) * bl; j++) { if (cnt[j] == 0) break; } ans.push_back(pii(p.id, j)); } sort(ans.begin(), ans.end()); for (auto p : ans) { cout << p.second << '\n'; } return 0; }
|