树上数据结构问题,多组询问,所有询问涉及的总点数与树的大小同阶。
这玩意儿就是在明示虚树嘛......
虚树建出来后,问题相当于**树上多源最短路**,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;
}
```