FULL
unknown
c_cpp
3 years ago
6.7 kB
5
Indexable
diam_parent[v] = diam_parent[p]; dp[v].add(0); for (auto to : g[v]) { if (in_DIAM[to] || to == p) continue; dfs(to, v); dp[v].add(dp[to]); } } void calc_self(int v, int p, int k = 0) { sz[v] = 1; self_val[v] = max(self_val[v], dp[v].diam); self_val[v] = max(self_val[v], k); k_max maxs = k_max(2), kek = k_max(3); for (auto to : g[v]) { if (in_DIAM[to] || to == p) continue; maxs.add(max(dp[to].diam, dp[to].farthest + 1), to); kek.add(dp[to].farthest + 1, to); } for (auto to : g[v]) { if (in_DIAM[to] || to == p) continue; int kk = k; kk = max(kk, maxs.get({to})); kk = max(kk, kek.get({to}, 2)); calc_self(to, v, kk); sz[v] += sz[to]; } } void calc_left(int v, int p, int k) { left_val[v] = max(self_val[v], k); for (auto to : g[v]) { if (in_DIAM[to] || to == p) continue; calc_left(to, v, k); } } void calc_right(int v, int p, int k) { right_val[v] = max(self_val[v], k); for (auto to : g[v]) { if (in_DIAM[to] || to == p) continue; calc_right(to, v, k); } } vector<ll> solve(int _n, vector<pii> edges, vector<pii> queries) { n = _n; for (auto edge : edges) { int v = edge.f; int u = edge.s; g[v].pb(u); g[u].pb(v); } A = get_farthest(1, 1); B = get_farthest(A, A); for (int v = B; v != A; v = parent[v]) DIAM.pb(v); DIAM.pb(A); for (int i = 0; i < DIAM.size(); i++) { int v = DIAM[i]; in_DIAM[v] = 1; in_DIAM_pos[v] = i; } for (int i = 0; i < DIAM.size(); i++) { int v = DIAM[i]; dfs(v, v); calc_self(v, v); } for (int i = 0, farthest = 0; i < DIAM.size(); i++) { int v = DIAM[i]; int prev = 0; left_val[v] = max(left_val[v], self_val[v]); if (i) { prev = left_val[DIAM[i - 1]]; farthest = farthest + 1; left_val[v] = max(left_val[v], prev); left_val[v] = max(left_val[v], farthest + dp[v].farthest); } k_max maxs = k_max(2); for (auto to : g[v]) { if (in_DIAM[to]) continue; maxs.add(dp[to].farthest + 1, to); } for (auto to : g[v]) { if (in_DIAM[to]) continue; calc_left(to, v, max(prev, farthest + maxs.get({to}))); } farthest = max(farthest, dp[v].farthest); } for (int i = DIAM.size() - 1, farthest = 0; i >= 0; i--) { int v = DIAM[i]; int prev = 0; right_val[v] = max(right_val[v], self_val[v]); if (i + 1 < DIAM.size()) { prev = right_val[DIAM[i + 1]]; farthest = farthest + 1; right_val[v] = max(right_val[v], prev); right_val[v] = max(right_val[v], farthest + dp[v].farthest); } k_max maxs = k_max(2); for (auto to : g[v]) { if (in_DIAM[to]) continue; maxs.add(dp[to].farthest + 1, to); } for (auto to : g[v]) { if (in_DIAM[to]) continue; calc_right(to, v, max(prev, farthest + maxs.get({to}))); } farthest = max(farthest, dp[v].farthest); } fen lefts, rights; for (int i = 1; i <= n; i++) { int pos = in_DIAM_pos[diam_parent[i]]; lefts.inc(pos, 1); rights.inc(pos, 1); events[m++] = {left_val[i], {0, i}}; events[m++] = {right_val[i], {1, i}}; } for (int i = 0; i < DIAM.size(); i++) { int v = DIAM[i]; events[m++] = {self_val[v], {2, v}}; } sort(events, events + m); reverse(events, events + m); set<int> blocked; blocked.insert(0); blocked.insert(DIAM.size() - 1); for (int i = 0; i < m; i++) { int val = events[i].f; int type = events[i].s.f; int pos = in_DIAM_pos[diam_parent[events[i].s.s]]; if (type == 0) { int l = pos + 1; int r = (*blocked.upper_bound(pos)); ans[val] += rights.get(l, r); lefts.inc(pos, -1); } if (type == 1) { int l = (*(--blocked.lower_bound(pos))); int r = pos - 1; ans[val] += lefts.get(l, r); rights.inc(pos, -1); } if (type == 2) { int l = (*(--blocked.lower_bound(pos))); int r = (*blocked.upper_bound(pos)); ans[val] += lefts.get(l, pos - 1) * rights.get(pos + 1, r); blocked.insert(pos); } } for (auto v : DIAM) ans[DIAM.size() - 1] += 1ll * sz[v] * (sz[v] - 1) / 2; k_max selfs = k_max(3); for (auto v : DIAM) selfs.add(self_val[v], v); vector<ll> result; for (auto query : queries) { if (query.f > 0) { int v = query.f; int u = query.s; int val = 0; if (diam_parent[v] == diam_parent[u]) val = max(val, (int)DIAM.size() - 1); if (in_DIAM_pos[diam_parent[v]] > in_DIAM_pos[diam_parent[u]]) swap(v, u); val = max(val, left_val[v]); val = max(val, right_val[u]); val = max(val, selfs.get({diam_parent[u], diam_parent[v]})); result.pb(val); } else { int k = query.s; result.pb(ans[k]); } } return result; } int main() { int n, m; vector<pii> edges; vector<pii> queries; scanf("%d", &n); for (int i = 1; i < n; i++) { int v, u; scanf("%d%d", &v, &u); edges.pb({v, u}); } scanf("%d", &m); for (int i = 0; i < m; i++) { int type; scanf("%d", &type); if (type == 1) { int v, u; scanf("%d%d", &v, &u); queries.pb({v, u}); } else { int k; scanf("%lld", &k); queries.pb({0, k}); } } vector<ll> ans = solve(n, edges, queries); for (auto val : ans) printf("%lld\n", val); return 0; }
Editor is loading...