Untitled
unknown
c_cpp
2 months ago
4.4 kB
3
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif constexpr int maxN = 1e5; constexpr int K = 320; struct mexsd { set<int> mex[K]; vector<int> cnt; mexsd() { cnt.assign(maxN + 1, 0); for (int i = 0; i < K; i++) { int L = i * K, R = (i + 1) * K; for (int j = L; j < R; j++) { mex[i].insert(j); } } } void add(int x) { if (x > maxN) return; cnt[x]++; if (cnt[x] == 1) { mex[x / K].erase(x); } } void remove(int x) { if (x > maxN) return; cnt[x]--; if (cnt[x] == 0) { mex[x / K].insert(x); } } int get_mex() { for (int i = 0; i < K; i++) { if (!mex[i].empty()) { return *mex[i].begin(); } } assert(false); } }; struct query { int l, r, t; }; void solve() { int n, q; cin >> n >> q; vector<vector<pair<int, int>>> graph(n); for (int i = 0; i < n - 1; i++) { int u, v, x; cin >> u >> v >> x; u--; v--; graph[u].emplace_back(v, x); graph[v].emplace_back(u, x); } vector<pair<int, int>> euler; euler.emplace_back(0, INT_MAX); auto dfs = [&](auto self, int v, int p) -> void { for (auto &[g, e] : graph[v]) { if (g != p) { euler.emplace_back(g, e); self(self, g, v); euler.emplace_back(v, e); } } }; dfs(dfs, 0, -1); vector<int> p(n, -1); for (int i = 0; i < (int)euler.size(); i++) { if (p[euler[i].first] == -1) { p[euler[i].first] = i; } } vector<query> queries(q); for (int i = 0; i < q; i++) { cin >> queries[i].l >> queries[i].r; queries[i].l--; queries[i].r--; queries[i].l = p[queries[i].l]; queries[i].r = p[queries[i].r]; queries[i].t = i; } sort(queries.begin(), queries.end(), [&](query &lhs, query &rhs) { return lhs.r / K < rhs.r / K || (lhs.r / K == rhs.r / K && lhs.l * (lhs.r / K % 2 ? -1 : 1) < rhs.l * (rhs.r / K % 2 ? -1 : 1)); }); vector<bool> way(n, false); way[0] = true; int l = 0, r = 0; // [l, r] in euler mexsd sd; vector<int> ans(q); for (auto &[ql, qr, t] : queries) { while (ql < l) { pair<int, int> nxtp = euler[l - 1]; pair<int, int> curp = euler[l]; if (way[nxtp.first]) { way[curp.first] = false; sd.remove(curp.second); } else { way[nxtp.first] = true; sd.add(nxtp.second); } l--; } while (qr > r) { pair<int, int> nxtp = euler[r + 1]; pair<int, int> curp = euler[r]; if (way[nxtp.first]) { way[curp.first] = false; sd.remove(curp.second); } else { way[nxtp.first] = true; sd.add(nxtp.second); } r++; } while (ql > l) { pair<int, int> nxtp = euler[l + 1]; pair<int, int> curp = euler[l]; if (way[nxtp.first]) { way[curp.first] = false; sd.remove(curp.second); } else { way[nxtp.first] = true; sd.add(nxtp.second); } l++; } while (qr < r) { pair<int, int> nxtp = euler[r - 1]; pair<int, int> curp = euler[r]; if (way[nxtp.first]) { way[curp.first] = false; sd.remove(curp.second); } else { way[nxtp.first] = true; sd.add(nxtp.second); } r--; } debug(way); ans[t] = sd.get_mex(); } for (int &i : ans) { cout << i << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }