题解 CF1320E 【Treeland and Viruses】

xht

2020-03-03 15:13:25

Solution

树上数据结构问题,多组询问,所有询问涉及的总点数与树的大小同阶。 这玩意儿就是在明示虚树嘛...... 虚树建出来后,问题相当于**树上多源最短路**,dijkstra 即可。 ```cpp const int N = 2e5 + 7; int n, q, dfn[N], tot, f[N][21], d[N], s[N], t; vi e[N], g[N]; void dfs(int x) { dfn[x] = ++tot; for (int y : e[x]) if (y != f[x][0]) { d[y] = d[x] + 1, f[y][0] = x; for (int i = 1; f[y][i-1]; i++) f[y][i] = f[f[y][i-1]][i-1]; dfs(y); } } inline int lca(int x, int y) { if (d[x] > d[y]) swap(x, y); for (int i = 20; ~i; i--) if (d[f[y][i]] >= d[x]) y = f[y][i]; if (x == y) return x; for (int i = 20; ~i; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } inline void virtual_tree(vi &p) { sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); p.erase(unique(p.begin(), p.end()), p.end()); vi q = p; for (int x : p) { int lca = ::lca(x, s[t]); if (lca != s[t]) { while (t && d[s[t-1]] >= d[lca]) g[s[t]].pb(s[t-1]), g[s[t-1]].pb(s[t]), --t; if (s[t] != lca) g[s[t]].pb(lca), g[lca].pb(s[t]), s[t] = lca, q.pb(lca); } s[++t] = x; } if (t) while (--t) g[s[t]].pb(s[t+1]), g[s[t+1]].pb(s[t]); p = q; } int w[N]; bool v[N]; struct P { int d, i, x, r; inline P() {} inline P(int d, int i, int x) : d(d), i(i), x(x) { r = d ? (d - 1) / w[x] : -1; } inline bool operator < (const P o) const { return r == o.r ? i < o.i : r < o.r; } inline P operator - () const { P o = *this; o.r *= -1, o.i *= -1; return o; } } u[N]; inline void dijkstra(vi a, vi b, vi p) { pq<pair<P, int>> q; for (int x : p) u[x].r = u[x].i = n, v[x] = 0; for (ui i = 0; i < a.size(); i++) u[a[i]] = P(0, i, a[i]), q.push(mp(-u[a[i]], a[i])); while (q.size()) { int x = q.top().se; q.pop(); if (v[x]) continue; v[x] = 1; for (int y : g[x]) { P o = P(u[x].d + abs(d[x] - d[y]), u[x].i, u[x].x); if (o < u[y]) u[y] = o, q.push(mp(-u[y], y)); } } for (int x : b) print(u[x].i + 1, ' '); prints(""); } int main() { rd(n); for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x); d[1] = 1, dfs(1); rd(q); while (q--) { int A, B; rd(A), rd(B); vi a, b, p; for (int i = 1, x, y; i <= A; i++) rd(x), rd(y), a.pb(x), p.pb(x), w[x] = y; for (int i = 1, x; i <= B; i++) rd(x), b.pb(x), p.pb(x); virtual_tree(p); dijkstra(a, b, p); for (int x : p) g[x].clear(); } return 0; } ```