有一棵有$n$个节点的树，$q$次询问（询问互相独立），每次给定$k_i$个颜色，每个颜色有一个起始点$v_j$和移动速度$s_j$每一个颜色在每一次操作中会使它周围没有被染色的连通块上与它的距离不超过$s_j$
的点全部染为这一个颜色，每一轮中，颜色从$1$到$k_i$
依次开始操作，一直到所有点全部被染色为止，再询问$m_i$个关键点的颜色。

显然是虚树的问题，转化一下。

你有一棵树, 有一些点已经被感染了, 每条边有边权, 求这棵树所有的点被哪种病毒感染

考虑简单的$BFS$,按照编号顺序扩展每一个点，然后每次可以更新一下。
可以整一整玄学的$SPFA$.

考虑$1\rightarrow 3$需要$3$秒,考虑$2\rightarrow 3$需要$2$秒,那么这个点都会被抓到，但是扩展$3$的时候是用$2$号病毒扩展，类似$disjstar$，我总是拿最优的先扩展，那么可以用优先队列优化.

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9;
int read()
{
int x = 0, F = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
F = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * F;
}

namespace Tree
{

int st[N][22], dfn[N], dep[N], tot, lg2[N];
vector<int> G[N];
void dfs(int x, int fa)
{
    st[++tot][0] = x;
    dep[x] = dep[fa] + 1;
    dfn[x] = tot;
    for (int to : G[x])
    {
        if (to == fa)
            continue;
        dfs(to, x);
        st[++tot][0] = x;
    }
}
int lower(int u, int v)
{
    return (dep[u] < dep[v]) ? u : v;
}

void Lca_init()
{
    dfs(1, 0);
    for (int i = 2; i <= tot; i++)
        lg2[i] = lg2[i >> 1] + 1;
    for (int l = 1; (1 << l) <= tot; l++)
    {
        for (int i = 1; i + (1 << l) - 1 <= tot; i++)
            st[i][l] = lower(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
    }
}
int lca(int u, int v)
{
    u = dfn[u];
    v = dfn[v];
    if (u > v)
        swap(u, v);
    int i = lg2[v - u + 1], w = (1 << i);
    return lower(st[u][i], st[v - w + 1][i]);
}
int dis(int u, int v)
{
    int lc = lca(u, v);
    return dep[u] + dep[v] - 2 * dep[lc];
}

}; // namespace Tree
using namespace Tree;

struct node
{
int u, t, c, d; // u表示点，t表示到达时间，c表示啥颜色，d表示经过的路程
};
inline bool operator<(node x, node y) { return x.t == y.t ? x.c > y.c : x.t > y.t; }
priority_queue q;
int col[N];

namespace XTree
{
stack s;
vector tmp;

int b[N];

vector<pii> g[N];

bool cmp(int x, int y)
{
    return Tree::dfn[x] < Tree::dfn[y];
}

void addEdge(int u, int v)
{

    int d = Tree::dis(u, v);

    g[u].push_back(mk(v, d));
    g[v].push_back(mk(u, d));
}

void build(int k)
{

    tmp.clear();
    while (!s.empty())
        s.pop();
    sort(b + 1, b + 1 + k, cmp);
    k = unique(b + 1, b + 1 + k) - b - 1;
    s.push(1);
    tmp.push_back(1);
    for (int i = 1; i <= k; ++i)
    {
        int x = b[i];
        tmp.push_back(x);
        int lca = Tree::lca(x, s.top());
        while (s.top() != lca)
        {
            int tmc = s.top();
            s.pop();
            if (dfn[s.top()] < dfn[lca])
                s.push(lca), tmp.push_back(lca);
            addEdge(s.top(), tmc);
        }
        s.push(x);
    }
    while (s.top() != 1)
    {
        int tmp = s.top();
        s.pop();
        addEdge(s.top(), tmp);
    }
}
void clear()
{
    for (int x : tmp)
    {
        g[x].clear();
        col[x] = 0;
    }
}

} // namespace XTree
int s[N], vt[N], ut[N];
void solve()
{

while (!q.empty())
{
    node o = q.top();
    q.pop();
    int x = o.u;
    if (col[x])
        continue;
    col[x] = o.c;
    for (pii now : XTree::g[x])
    {
        int to = now.first;
        int w = now.second;
        if (!col[to])
            q.push((node){to, (o.d + w - 1) / vt[o.c] + 1, o.c, o.d + w});
    }
}

}

int main()
{

int n = read();
for (int i = 1; i < n; i++)
{
    int u = read(), v = read();
    G[u].push_back(v);
    G[v].push_back(u);
}
Lca_init();
int Q = read();

while (Q--)
{
    int k = read(), m = read();
    int cnt = 0;
    for (int i = 1; i <= k; i++)
    {
        s[i] = read();
        vt[i] = read();
        XTree::b[++cnt] = s[i];
        q.push((node){s[i], 0, i, 0});
    }
    for (int i = 1; i <= m; i++)
    {
        ut[i] = read();
        XTree::b[++cnt] = ut[i];
    }
    XTree::build(cnt);
    solve();

    for (int i = 1; i <= m; i++)
    {
        printf("%d ", col[ut[i]]);
    }
    puts("");
    XTree::clear();
}

}