思路：

树形dp。

实现：

1 #include 
     
       2 using namespace std; 3 const int MAXN = 100005; 4 int n, a[MAXN], in[MAXN]; 5 vector
      
        G[MAXN]; 6 double dp[MAXN][2]; 7 bool vis[MAXN]; 8 void dfs(int now) 9 {10     vis[now] = true;11     for (int i = 0; i < G[now].size(); i++)12     {13         int tmp = G[now][i];14         if (!vis[tmp]) dfs(tmp);15         dp[now][0] += max(dp[tmp][0], dp[tmp][1] + a[tmp]);16         dp[now][1] += max(dp[tmp][0], dp[tmp][1] + (double)a[tmp] / 2.0);17     }    18 }19 int main()20 {21     cin >> n;22     int u, v;23     for (int i = 1; i <= n; i++) cin >> a[i];24     for (int i = 0; i < n - 1; i++) { cin >> u >> v; in[v]++; G[u].push_back(v); }25     int i = 1;26     for (; i <= n; i++) if (!in[i]) break;27     dfs(i);28     printf("%.1f\n", max(dp[i][0], dp[i][1] + a[i]));29     return 0;30 }