#include<iostream>
#include<cstring>
using namespace std;
const int N=60010;
int h[N],e[N],ne[N],idx;
int happy[N];
bool has_fa[N];
int f[N][2];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=happy[u];
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0],f[j][1]);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        has_fa[a]=true;
        add(b,a);
    }
    int root=1;
    while(has_fa[root]) root++;
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
}

@ans=(n−2)∑(xiwi)+∑xi∑wi

#include<iostream>
using namespace std;
const int N=100010,mod=10007;
//w[i]表示第i个格子的数字
//color[i]表示第i个格子的颜色
int w[N], color[N];
//sum[i][0]表示颜色为i、编号为偶数的格子上数字的前缀和
//cnt[i][0]表示颜色为i、编号为偶数的格子的个数
int sum[N][2], cnt[N][2];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        cin>>color[i];
        sum[color[i]][i%2]=(sum[color[i]][i%2]+w[i])%mod;
        cnt[color[i]][i%2]++;
    }

    long long ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+i*((cnt[color[i]][i%2]-2)*w[i]%mod+sum[color[i]][i%2]))%mod;
    }

    cout<<ans<<endl;
}

#include<iostream>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int N=100010;
bool cmp(pair<LL,LL>a,pair<LL,LL>b)
{
    return a.first+a.second>b.first+b.second;
}
int main()
{
    int n;
    cin>>n;
    vector<pair<LL,LL>>a(n);
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        a[i]={x,y};
    }
    sort(a.begin(),a.end(),cmp);
    vector<LL>sum(n+1,0);
    for(int i=n-1;i>=0;i--){
        sum[i]=sum[i+1]+a[i].first;
    }
    LL ans=-1e10;
    for(int i=0;i<n;i++){
        ans=max(ans,sum[i+1]-a[i].second);
    }
    cout<<ans;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N=100010;

typedef long long LL;

int n;
int a[N];

int main(){
    scanf("%d",&n);

    LL tmp=0;

    for(int i=0;i<n;i++) scanf("%d ",&a[i]);

    sort(a,a+n);

    for(int i=0;i<n;i++) tmp +=abs(a[i]-a[n/2]);

    printf("%lld",tmp);

    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main()
{
    int n;
    cin>>n;
    long long ans=0;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n,greater<int>());
    for(int i=0;i<n;i++){
        ans+=a[i]*i;
    }
    cout<<ans;
}

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int n;
    cin>>n;
    priority_queue<long long,vector<long long>,greater<long long>>h;
    while(n--){
        int x;
        cin>>x;
        h.push(x);
    }
    long long ans=0;
    while(h.size()>1){
        long long a=h.top();
        h.pop();
        long long b=h.top();
        h.pop();
        a+=b;
        ans+=a;
        h.push(a);
    }
    cout<<ans;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct tem{
    int l,r;
    bool operator < (const tem M){
        return l<M.l;
    }
}renge[N];
int main()
{
    int st,ed,n;
    cin>>st>>ed;
    cin>>n;
    for(int i=0;i<n;i++) cin>>renge[i].l>>renge[i].r;
    sort(renge,renge+n);
    int ans=0;
    bool success=false;
    for(int i=0;i<n;i++){
        int j=i,r=-2e9;
        while(j<n&&renge[j].l<=st){
            r=max(r,renge[j].r);
            j++;
        }
        if(r<st){
            ans=-1;
            break;
        }
        ans++;
        if(r>=ed){
            success=true;
            break;
        }
        st=r;
        i=j-1;
    }
    if(!success) ans=-1;
    cout<<ans;
    return 0;
}

#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;
const int Maxn = 1e5 + 5;
int n, a[Maxn], b[Maxn], i, ans = 0, j = 0;
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d %d", a + i, b + i);
    }
    sort(a, a + n);
    sort(b, b + n);
    for (i = 0; i < n; i++) {
        if (a[i] <= b[j])
            ans++;
        else
            j++;
    }
    printf("%d\n", ans);
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct Range{
    int l,r;
    bool operator< (const Range& w){
        return r<w.r;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>range[i].l>>range[i].r;
    }
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct Range{
    int l,r;
    bool operator< (const Range& w){
        return r<w.r;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>range[i].l>>range[i].r;
    }
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
}