int id[N],nw[N],cnt_id;
int dep[N],sz[N],top[N],fa[N],son[N];
struct Tree{
    int l,r;
    long long add,sum;
}tr[4*N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//求出sz,son,dep,fa
void dfs1(int father,int u,int depth){
    dep[u]=depth,fa[u]=father,sz[u]=1;

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father) continue;

        dfs1(u,j,depth+1);
        sz[u]+=sz[j];
        if(sz[son[u]]<sz[j]) son[u]=j;
    }
}

//求出id,nw,top
void dfs2(int u,int t){
    id[u]=++cnt_id,nw[cnt_id]=w[u],top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u]) continue;

        dfs2(j,j);
    }
}

void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}


void pushdown(int u){
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];

    if(root.add){
        left.add+=root.add,left.sum+=root.add*(left.r-left.l+1);
        right.add+=root.add,right.sum+=root.add*(right.r-right.l+1);
        root.add=0;
    }
}

void build(int root,int l,int r){
    tr[root]={l,r,0,nw[r]};
    if(l==r) return;

    int mid=l+r>>1;
    build(root<<1,l,mid),build(root<<1|1,mid+1,r);
    pushup(root);
}

void update(int u,int l,int r,int k){
    if(l<=tr[u].l&&r>=tr[u].r){
        tr[u].add+=k;
        tr[u].sum+=k*(tr[u].r-tr[u].l+1);
        return;
    }

    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) update(u<<1,l,r,k);
    if(r>mid) update(u<<1|1,l,r,k);
    pushup(u);
}

long long query(int u,int l,int r){
    if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;

    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    long long ans=0;
    if(l<=mid) ans+=query(u<<1,l,r);
    if(r>mid)  ans+=query(u<<1|1,l,r);

    return ans;
}

//u,v之间路径加上每个节点k
void update_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        update(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }

    if(dep[u]<dep[v]) swap(u,v);
    update(1,id[v],id[u],k);
}

//查询u，v之间节点总和
long long query_path(int u,int v){
    long long ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ans+=query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }

    if(dep[u]<dep[v]) swap(u,v);
    ans+=query(1,id[v],id[u]);

    return ans;
}


//将u为根的树每个节点加上k
void update_tree(int u,int k){
    update(1,id[u],id[u]+sz[u]-1,k);
}

//查询u为根的树每个节点总和
long long query_tree(int u){
    return query(1,id[u],id[u]+sz[u]-1); 
}