#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5+10,M = 20,INF = 1e18;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
typedef vector<ll> vec; typedef vector<int> vi; typedef array<ll,2> pr;
int n,vis[MAXN]; ll a[MAXN],b[MAXN],dis[MAXN];
vector<pr> e[MAXN];

priority_queue<pr> pq;

int rt;
int sz[MAXN],tag[MAXN],dep[MAXN],fa[MAXN];

int cnt[MAXN],cur[MAXN]; ll wdis[MAXN][M];

vector<int> o[MAXN];

void rfind(int u,int fa,int all,int& r){
    sz[u] = 1; int mx = 0; 
    for(auto [v,w] : e[u])if(v != fa && !tag[v]){
        rfind(v,u,all,r);
        sz[u] += sz[v]; tomax(mx,sz[v]);
    }
    tomax(mx,all-sz[u]); if(mx <= all/2)r = u;
}
void rdfs(int u,int fa,int p){
    sz[u] = 1; o[p].push_back(u); cnt[p]++;
    for(auto [v,w] : e[u])if(v != fa && !tag[v]){
        wdis[v][dep[p]] = wdis[u][dep[p]] + w;
        rdfs(v,u,p);
        sz[u] += sz[v];
    }
}

int build(int u,int all,int d){
    rfind(u,0,all,u);
    dep[u] = d; tag[u] = 1;
    rdfs(u,0,u);
    sort(o[u].begin(),o[u].end(),[&](int x,int y){return wdis[x][d] < wdis[y][d];});
    for(auto [v,w] : e[u])if(!tag[v]){
        int p = build(v,sz[v],d+1);
        fa[p] = u;
    }
    return u;
}

vector<pr> arr[MAXN];
void ext(int u){
    for(int p=u;p;p=fa[p]){
        while(cur[p] < cnt[p] && vis[o[p][cur[p]]])cur[p]++;
        //插入线段
        int d = dep[p];
        arr[p].push_back((pr){b[u],b[u] * wdis[u][d] + a[u] + dis[u]});
        if(cur[p] < cnt[p]){
            int v = o[p][cur[p]]; 
            ll mn = INF;
            for(auto [k,b] : arr[p])tomin(mn,k * wdis[v][d] + b);
            if(mn < dis[v]){
                dis[v] = mn;
                pq.push((pr){-dis[v],v});
            }
        }
    }
}

vec travel(vec A,vi B,vi U,vi V,vi W){
    n = A.size();
    for(int i=1;i<=n;i++)a[i] = A[i-1],b[i] = B[i-1];
    for(int i=0;i<n-1;i++){
        int u = U[i],v = V[i],w = W[i];
        u++; v++;
        e[u].push_back({v,w}); e[v].push_back({u,w});
    }
    fill(dis+1,dis+1+n,INF);
    //建立点分树
    rt = build(1,n,0);

    dis[1] = 0; pq.push((pr){0,1});
    while(pq.size()){
        pr now = pq.top(); pq.pop();
        int u = now[1]; if(vis[u])continue; 
        vis[u] = 1;
        ext(u);
    }

    //
    vec ans; for(int i=2;i<=n;i++)ans.push_back(dis[i]); return ans;
}

int main(){
    vec tmp = travel((vec){10,5,13,4,3},(vi){10,7,5,9,1},(vi){1,0,3,2},(vi){0,2,2,4},(vi){1,5,10,3});
    for(auto u : tmp)cout<<u<<" ";

    return 0;
}

answer.code: In function ‘void rfind(int, int, int, int&)’:
answer.code:22:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   22 |     for(auto [v,w] : e[u])if(v != fa && !tag[v]){
      |              ^
answer.code: In function ‘void rdfs(int, int, int)’:
answer.code:30:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   30 |     for(auto [v,w] : e[u])if(v != fa && !tag[v]){
      |              ^
answer.code: In function ‘int build(int, int, int)’:
answer.code:42:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   42 |     for(auto [v,w] : e[u])if(!tag[v]){
      |              ^
answer.code: In function ‘void ext(int)’:
answer.code:59:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   59 |             for(auto [k,b] : arr[p])tomin(mn,k * wdis[v][d] + b);
      |                      ^
/usr/bin/ld: /tmp/ccXT2KCt.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cci3sdQs.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status