题解

· · 题解

include <bits/stdc++.h>

using namespace std; const int N = 1e5 + 5, LG = 19; int n, m, ld[N], rd[N], idx; int rt[N], ls[N LG], rs[N LG], sum[N * LG], tot; vector<int> g[N]; inline int modify(int pre, int l, int r, int x, int k) { int p = ++tot; ls[p] = ls[pre], rs[p] = rs[pre], sum[p] = sum[pre] + k; if (l == r) return p; int mid = (l + r) >> 1; if (x <= mid) ls[p] = modify(ls[pre], l, mid, x, k); else rs[p] = modify(rs[pre], mid + 1, r, x, k); return p; } inline int query(int u, int v, int l, int r, int L, int R) { if (L <= l && r <= R) return sum[v] - sum[u]; int mid = (l + r) >> 1, res = 0; if (L <= mid) res += query(ls[u], ls[v], l, mid, L, R); if (R > mid) res += query(rs[u], rs[v], mid + 1, r, L, R); return res; } inline void dfs(int u, int fr, int dep) { ld[u] = ++idx, rt[idx] = modify(rt[idx - 1], 1, n, dep, 1); // cerr << u << ' ' << dep << '\n'; for (int v : g[u]) if (v != fr) dfs(v, u, dep + 1); rd[u] = idx; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } dfs(1, 0, 1); int curx = n + 1; for (int i = 1; i <= m; i++) { int op, x; cin >> op >> x; if (op == 1) { curx = x; } else { if (curx == n + 1) cout << "0\n"; else cout << query(rt[ld[x] - 1], rt[rd[x]], 1, n, curx, n) << '\n'; } } return 0; }

为了防止抄袭，这里有乱码 4576379821434#@$#@#!@3345678903t12725641623456789876543456789032323@!31736126372`192736543678290091-3