地图上的 n个城市，由 n-1条道路连接，且任意两个城市连通。
除 1号城市之外的每个都有 一台计算机，安装软件号城市之外的每个都有 一台计算机，安装软件一个 自己的安装时间。
住在 1号城市的蒟蒻要给这 n-1台计算机装配软件，他可以沿着 n-1条道路 行走，每条道路花费的时间为 1。
蒟蒻在第 0时刻出发，他每走到一个城市就立给该的电脑装软件。
因为蒟蒻急着回家，所以他希望在最快到，因为蒟蒻急着回家，所以他希望在最快到 1号城市的基础上，所有电脑完 号城市的基础上，所有电脑完成。
【数据规模和约定】
对于 30%的数据，2<=n<=10，1<=每台计算机安装软件时间<=100；
对于 60%的数据，2<=n<=1000，1<=每台计算机安装软件时间<=100000；
对于 100%的数据，2<=n<=500000，1<=每台计算机安装软件的时间<=10^9。
注意一定要保证回去时间最小，图又是一颗树，所以每条边一定经过两次，而一旦到达一个点，一定要遍历完当前点的所有子树再返回。
这道题设L[k]为从k开始，按照最优决策遍历完所有k的子树，所有软件完成安装所需的最小时间。s[k]是k的子树大小。
注意到这样一个问题，若当前节点有两种选择，1和2，我们所需要做的决策就是
max(l[1],l[2]+2*s[1]),max(l[1]+2*s[2],l[2])这两个数哪一个小，就选小的决策，其中第一个代表先走1，第二个代表先走2。
假设一个节点有q个子树，我们做出了q个决策，那么显然，交换任意两个相邻的决策顺序不会影响其它决策，然后多做几次，选出一个最优的决策。
我的方法是证明在这q个子树中，第一步要么走l最大的，要么走l次大的。因为不走l最大的的原因是其size过大，而毫无疑问，这个事件对l次大的影响是最大的，所以结论成立。
然后按l排序，for i=2 to n，判断每个和第1个哪个更优，更优的就取走，bas+=2*s[k]，剩下的没被取走的就作为第一个。
PS：这题略卡常，用vector存图会TLE
#include<cstdio>
#include<algorithm>
#define maxn 500005
using namespace std;
int fa[maxn];
long long size[maxn],x[maxn],t[maxn],n,m,head[maxn],cnt,sf[maxn];
struct edge{int to,next;}e[*maxn];
void insert(int u,int v){
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
struct sd{
int u;long long v;
bool operator < (const sd & g1) const{
return v>g1.v;}
}q[*maxn];
long long read(){
long long ret=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') ret=ret*+ch-'',ch=getchar();
return ret;
}
void dfs(int k,int f){
fa[k]=f;
for(int i=head[k];i;i=e[i].next){
if(e[i].to==f) continue;
dfs(e[i].to,k);
size[k]+=size[e[i].to];
}size[k]++;
}
void dfs2(int k,int bas){
long long h,tot=bas;
for(int i=head[k];i;i=e[i].next){
if(e[i].to==fa[k]) continue;
dfs2(e[i].to,tot);tot++;
q[tot].u=e[i].to;
q[tot].v=t[e[i].to];
}
t[k]=max(t[k],sf[k]);
if(!(tot-bas)) return;
sort(q+bas+,q+tot+);long long bsi=;
for(int i=bas+;i<=tot;i++){
if(q[bas+].v+*size[q[i].u]<q[i].v+*size[q[bas+].u]){
t[k]=max(t[k],q[i].v+bsi);
bsi+=*size[q[i].u];
}
else{
t[k]=max(t[k],q[bas+].v+bsi);
bsi+=*size[q[bas+].u];
q[bas+].v=q[i].v;q[bas+].u=q[i].u;
}
}
t[k]=max(t[k],t[q[bas+].u]+bsi);
}
int main(){
freopen("software.in","r",stdin);
freopen("software.out","w",stdout);
n=read();
for(int i=;i<=n;i++)sf[i]=read();long long a,b;
for(int i=;i<n;i++){
a=read();b=read();
insert(a,b);
}
dfs(,);
dfs2(,);
printf("%lld\n",t[]);
return ;
}