>
> --- Wookieepedia
Though being cruel and merciless in the battlefields, the total obedience to the command hierarchy makes message delivering between Stormtroopers quite inefficient, which finally caused the escape of Luke Skywalker, the destroy of the Death Star, and the collapse of the Galactic Empire.
In particular, the hierarchy of Stormtroopers is defined by a *binary tree*. Everyone in the tree has at most two direct subordinates and exactly one direct leader, except the first (numbered 1) Stormtrooper, who only obey the order of the Emperor.
It has been a time-consuming task for the Stormtroopers to input messages into his own log system. Suppose that the i-th Stormtrooper has a message of length ai, which means that it costs ai time to input this message into a log system. Everyone in the hierarchy has the mission of collecting all messages from his subordinates (a direct or indirect children in the tree) and input thses messages and his own message into his own log system.
Everyone in the hierarchy wants to optimize the process of inputting. First of all, everyone collects the messages from all his subordinates. For a Stormtrooper, starting from time 0, choose a message and input it into the log system. This process proceeds until all messages from his subordinates and his own message have been input into the log system. If a message is input at time t, it will induce t units of penalty.
For every Stormtrooper in the tree, you should find the minimum penalty.
In each case, there are a number n (1≤n≤105) in the first line, denoting the size of the tree.
The next line contains n integers, the i-th integer denotes ai (0≤ai≤108), the i-th Stormtrooper’s message length.
The following n−1 lines describe the edges of the tree. Each line contains two integers u,v (1≤u,v≤n), denoting there is an edge connecting u and v.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N=1e5+;
int w[N];
int val[N],id[N];
int sz[N],lson[N],rson[N],tot;
vector<int>e[N];
LL num[N],sum[N];
LL ans[N],tmp; int calSize(int now,int pre)
{
sz[now]=;
for(int j=;j<e[now].size();j++)
{
int to=e[now][j];
if(to==pre) continue;
if(!lson[now]) lson[now]=to;
else rson[now]=to;
sz[now]+=calSize(to,now);
}
if(lson[now]&&rson[now]&&sz[lson[now]]>sz[rson[now]])
swap(lson[now],rson[now]);
return sz[now];
}
int lowbit(int x)
{
return x&(-x);
}
void update(LL *a,int x,int y)
{
while(x<=tot)
{
a[x]+=(LL)y;
x+=lowbit(x);
}
}
LL query(LL *a,int x)
{
LL r=;
while(x)
{
r+=a[x];
x-=lowbit(x);
}
return r;
} void add(int x)
{
tmp+=(query(num,tot)-query(num,id[x]))*(LL)w[x]+(LL)w[x];
tmp+=query(sum,id[x]);
update(num,id[x],);
update(sum,id[x],w[x]);
}
void del(int x)
{
update(num,id[x],-);
update(sum,id[x],-w[x]);
tmp-=(query(num,tot)-query(num,id[x]))*(LL)w[x]+(LL)w[x];
tmp-=query(sum,id[x]);
}
void cle(int x)
{
del(x);
if(lson[x]) cle(lson[x]);
if(rson[x]) cle(rson[x]);
}
void validate(int x)
{
add(x);
if(lson[x]) validate(lson[x]);
if(rson[x]) validate(rson[x]);
}
void dfs(int now)
{
if(!lson[now])
{
ans[now]=(LL)w[now];
add(now);
return ;
}
dfs(lson[now]);
if(rson[now])
{
cle(lson[now]);
dfs(rson[now]);
validate(lson[now]);
}
add(now);
ans[now]=tmp;
}
int main()
{
int T; cin>>T;
while(T--)
{
int n; scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&w[i]);
val[i]=w[i];
e[i].clear();
num[i]=sum[i]=;
lson[i]=rson[i]=;
}
sort(val+,val+n+);
tot=unique(val+,val+n+)-val-;
for(int i=;i<=n;i++)
{
id[i]=lower_bound(val+,val+tot+,w[i])-val;
}
for(int i=;i<n;i++)
{
int u,v; scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
calSize(,-);
tmp=;
dfs();
for(int i=;i<=n;i++)
printf("%lld ",ans[i]);
puts("");
}
return ;
}