#include "virus.h"
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;
const int M = 5000005;

int n, m, cnt, val[N], vis[M];
long long dis[M];

vector <int> e[N];
vector < pair <int, int> > E[M], t[N];
priority_queue < pair <long long, int> > q;

void dijkstra()
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    q.push(make_pair(dis[1] = 0, 1));
    
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = 1;
        for(auto [v, w] : E[u])
            if(dis[v] > dis[u] + w)
                dis[v] = dis[u] + w, q.push({- dis[v], v});
    }
}

int rt, sum, MinId, MaxDep, siz[N], Max[N], dep[N], p[N][2];

void find(int u, int fa)
{
    siz[u] = 1;
    Max[u] = 0;
    for(int v : e[u])
    {
        if(v == fa || vis[v])
            continue;
        find(v, u);
        siz[u] += siz[v];
        Max[u] = max(Max[u], siz[v]);
    }
    Max[u] = max(Max[u], sum - siz[u]);
    rt = Max[u] < Max[rt] ? u : rt;
}

void getDis(int u, int fa)
{
    MaxDep = max(MaxDep, dep[u]);
    if(p[dep[u]][0] <= MinId)
    {
        p[dep[u]][0] = ++ cnt;
        if(dep[u] > 0)
            E[cnt].push_back({p[dep[u] - 1][0], 0});
        p[dep[u]][1] = ++ cnt;
        if(dep[u] > 0)
            E[p[dep[u] - 1][1]].push_back({cnt, 0});
    }
    E[p[dep[u]][0]].push_back({u + m, val[u]});
    E[u + m].push_back({p[dep[u]][1], 0});
    for(int v : e[u])
        if(!vis[v] && v != fa)
            dep[v] = dep[u] + 1, getDis(v, u);
}

void getEdge(int u, int fa)
{
    for(auto [x, y] : t[u])
    {
        if(y >= dep[u])
        {
            E[x].push_back({p[min(MaxDep, y - dep[u])][0], 0});
            E[p[min(MaxDep, y - dep[u])][1]].push_back({x, 0});
        }
    }
    for(int v : e[u])
        if(!vis[v] && v != fa)
            getEdge(v, u);
}

void solve(int u)
{
    MinId = cnt;
    dep[u] = MaxDep = 0;
    getDis(u, 0);
    getEdge(u, 0);
}

void division(int u)
{
    vis[u] = 1;
    solve(u);
    for(int v : e[u])
        if(!vis[v])
            sum = Max[rt = 0] = siz[v], find(v, u), division(rt);
}

vector <long long> ans;

vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C)
{
    n = N;
    m = M;
    for(int i = 0; i < N - 1; ++ i)
    {
        e[A[i] + 1].push_back(B[i] + 1);
        e[B[i] + 1].push_back(A[i] + 1);
    }
    for(int i = 0; i < M; ++ i)
        t[P[i] + 1].push_back({i + 1, D[i]}), E[P[i] + 1 + M].push_back({i + 1, 0});
    for(int i = 0; i < N; ++ i)
        val[i + 1] = C[i];

    cnt = n + m;
    sum = Max[rt = 0] = N;
    find(1, 0);
    division(rt);

    dijkstra();

    for(int i = 1; i <= M; ++ i)
        ans.push_back(dis[i] == dis[0] ? -1 : dis[i]);
    return ans;
}

answer.code:1:10: fatal error: virus.h: No such file or directory
    1 | #include "virus.h"
      |          ^~~~~~~~~
compilation terminated.