/**
 *    hello
 *    author:  N29
 *    created: 2024-06-15 10:57:27
**/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
// #define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=1e5+100;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e18+1;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
ll n,m;
ll ans[N];
ll c[N];
int p[N];
ll d[N*40];
vector<int>g[N];
vector<pair<int,ll>>f[N],G[N*40];
int sz[N];
bool mark[N];
void procsz(int x,int p){
    sz[x]=1;
    for(auto i:g[x]){
        if(i!=p&&!mark[i]){
            procsz(i,x);
            sz[x]+=sz[i];
        }
    }
}
int centroid(int x,int p,int &k){
    for(auto i:g[x]){
        if(i!=p&&!mark[i]&&k/2<=sz[i]){
            return centroid(i,x,k);
        }
    }
    return x;
}
vector<pair<int,int>>have,need;
void dfs(int x,int p,int h){
    have.push_back({h,x});
    for(auto [dep,i]:f[x]){
        if(dep-h>=0){
            need.push_back({dep-h,i});
        }
    }
    for(auto i:g[x]){
        if(!mark[i]&&i!=p){
            dfs(i,x,h+1);
        }
    }
}
ll tim=0;
ll fake[N*40],real_[N*40];
void decomp(int x=1){
    procsz(x,x);
    x=centroid(x,x,sz[x]);
    mark[x]=1;
    for(auto i:g[x]){
        if(!mark[i]){
            dfs(i,x,1);
        }
    }
    have.push_back({0,x});
    for(auto [dep,i]:f[x]){
        need.push_back({dep,i});
    }
    sort(have.begin(),have.end());
    sort(need.begin(),need.end());
    for(int i=0;i<have.size();i++){
        real_[i]=++tim;
    }
    for(int i=0;i<have.size();i++){
        auto [dep,j]=have[i];
        fake[i]=++tim;
        G[real_[i]].push_back({j,c[j]});
        G[j].push_back({fake[i],0});
        if(i>0){
            G[real_[i]].push_back({real_[i-1],0});
            G[fake[i-1]].push_back({fake[i],0});
        }
    }
    for(int i=0,j=0;i<need.size();i++){
        auto [dep,k]=need[i];
        for(;j<have.size()&&have[j].first<=need[i].first;j++){
            //bruh
        }
        if(j>0){
            G[k].push_back({real_[j-1],0});
            G[fake[j-1]].push_back({k,0});
        }
    }
    have.clear();
    need.clear();
    for(auto i:g[x]){
        if(!mark[i]){
            decomp(i);
        }
    }


}
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++){
        A[i]++;
        B[i]++;
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    for(int i=1;i<=n;i++){
        c[i]=C[i-1];
    }
    for(int i=1;i<=m;i++){
        p[i]=P[i-1]+1;
        d[i]=D[i-1];
        f[p[i]].push_back({d[i],n+i});
    }
    tim=n+m;
    decomp();
    for(int i=0;i<=tim;i++){
        d[i]=INF;
    }
    set<pair<ll,int>>s;
    s.insert({0,n+1});
    d[n+1]=0;
    while(s.size()){
        auto [w2,x]=*s.begin();
        s.erase(s.begin());
        for(auto [i,w]:G[x]){
            if(d[x]+w<d[i]){
                s.erase({d[i],i});
                d[i]=d[x]+w;
                s.insert({d[i],i});
            }
        }
    }
    vector<ll>t;
    for(int i=1;i<=m;i++){
        t.push_back(d[n+i]);
        if(t.back()==INF){
            t.pop_back();
            t.push_back(-1);
        }
    }
    return t;
}
/*
8 5

0 1
1 2
2 3
3 4 
4 5
5 6
6 7

2 2
5 0
7 0
1 1
4 1

40 5 5 16 32 8 1 10
//
8 5 

0 1
1 2
2 3
3 4
4 5 
3 6
3 7

2 2
5 0
7 0
1 1 
4 1

40 5 5 16 32 8 1 10
*/