一道虚树的题。
很明显，要对于每一次询问把相关的点拿出来建立一颗虚树。对于一次询问，使用最短路求解，处理一下堆里的排序规则即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int read()
{
int a = 0,x = 1;char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
return a*x;
}
const int N = 1e6+7;
int n,head[N],go[N],nxt[N],cnt,val[N],fa[N][20],dep[N],dfn[N];
void add(int u,int v,int w)
{
go[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
val[cnt] = w;
// if(w) printf("%d->%d,dis = %d
",u,v,w);
}
int LCA(int a,int b)
{
if(dep[a] < dep[b]) swap(a,b);
for(int i = 19;i >= 0;i --) if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
if(a == b) return a;
for(int i = 19;i >= 0;i --) if(fa[a][i] != fa[b][i]) a = fa[a][i],b = fa[b][i];
return fa[a][0];
}
void dfs(int u)
{
dep[u] = dep[fa[u][0]] + 1;dfn[u] = ++cnt;
for(int i = 1;i < 20;i ++) fa[u][i] = fa[fa[u][i-1]][i-1];
for(int e = head[u];e;e = nxt[e]) {
int v = go[e];if(v == fa[u][0]) continue;
fa[v][0] = u;dfs(v);
}
}
vector<int>g,f;
int s[N],stk[N],top,id[N],col[N],vis[N],dis[N];
bool cmp(int a,int b) {return dfn[a] < dfn[b];};
struct node{
int u,dis,c;
friend bool operator < (node a,node b) {return (a.dis+s[a.c]-1)/s[a.c] == (b.dis+s[b.c]-1)/s[b.c] ? id[a.c] > id[b.c] : (a.dis+s[a.c]-1)/s[a.c] > (b.dis+s[b.c]-1)/s[b.c];}
};
priority_queue<node>q;
void solve()
{
int k = read(),m = read();g.clear();//puts("=====");
while(!q.empty()) q.pop();cnt = 0;
for(int i = 1;i <= k;i ++) {
int u = read();s[u] = read();id[u] = i;
head[u] = 0;g.push_back(u);q.push((node){u,0,u});
}
f.clear();
for(int i = 1;i <= m;i ++) {
int a = read();g.push_back(a);f.push_back(a);head[a] = 0;
}
sort(g.begin(),g.end(),cmp);
head[stk[top = 1] = 1] = 0;vis[1] = 0;
for(auto a:g) {
int lca = LCA(a,stk[top]);vis[lca] = vis[a] = 0;
while(top > 1 && dep[lca] < dep[stk[top-1]]) {add(stk[top],stk[top-1],dep[stk[top]]-dep[stk[top-1]]),add(stk[top-1],stk[top],dep[stk[top]]-dep[stk[top-1]]);-- top;}
if(top && dep[stk[top]] > dep[lca]) {add(stk[top],lca,dep[stk[top]]-dep[lca]),add(lca,stk[top],dep[stk[top]]-dep[lca]);-- top;}
if(stk[top] != lca) stk[++top] = lca;if(stk[top] != a) stk[++top] = a;
}
while(top>1) {
add(stk[top],stk[top-1],dep[stk[top]]-dep[stk[top-1]]);
add(stk[top-1],stk[top],dep[stk[top]]-dep[stk[top-1]]);
-- top;
}
while(!q.empty()) {
int u = q.top().u;
if(vis[u]) {q.pop();continue ;}
dis[u] = q.top().dis,col[u] = q.top().c;vis[u] = 1;
q.pop();//printf("u = %d,dis[u] = %d,col[u] = %d
",u,dis[u],col[u]);
for(int e = head[u];e;e = nxt[e]) {
int v = go[e];if(vis[v]) continue;
q.push((node){v,dis[u]+val[e],col[u]});
}
head[u] = 0;
}
// printf("m = %d
",m);
for(auto a:f) printf("%d ",id[col[a]]);
puts("");
}
int main()
{
//freopen("random.in","r",stdin);freopen("sol.out","w",stdout);
n = read();
for(int i = 1;i < n;i ++) {
int u = read(),v = read();
add(u,v,0);add(v,u,0);
}
cnt = 0;dfs(1);int q = read();
for(int i = 1;i <= n;i ++) head[i] = 0;
while(q --) solve();
}