Spring Tree

There are $n$ iron balls numbered $1$ to $n$ , and the weight of the $i$ th ball is $w_i$ . We use $n - 1$ springs to connect them into a tree.

The ball numbered $1$ is the root of the tree. Now we grasp the root and hang the whole tree.

The initial length of each spring is $1$ . If the weight of the subtree it hangs is $g$ , its length will become $1 + g$ .

At this time, PaiGuDragon come up with an evil idea. It plans to rearrange the $w$ sequence, that is, PaiGuDragon is going to generate an array $p_1,p_2,...,p_n$ which is a permutation of $1,2....,n$ , and then the weight of the $i$ th ball will become $w_{p_i}$

Considering all the arrangements, what is the maximum of maximum depth of the tree after hanging?

Here, the maximum depth is defined as the maximum value of the sum of the spring lengths on the path from the leaf to the root.

The first line contains an integer $n(1\le n \le 100000)$ .

The second line contains $n$ integers $w_1,w_2,....,w_n (1\le w_i \le 10^9)$ - the initial state of weight.

Each of the next $n-1$ lines contains 2 integers $u, v(1\le u,v \le n)$ - an edge between $u,v$ .

It's guaranteed that the given graph is a tree.

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100007; int n; ll sum[N]; ll w[N]; vector<int>G[N]; ll dp[N]; ll ans=0; int sz[N]; void dfs(int x,int fa) { sz[x]=1; for(auto i:G[x]) { if(i==fa)continue; dfs(i,x); sz[x]+=sz[i]; dp[x]=max(dp[x],dp[i]); } dp[x]+=sum[n]-sum[n-sz[x]]+1; if(x!=1)ans=max(ans,dp[x]); } int main() { cin>>n; for(int i=1;i<=n;i++)cin>>w[i]; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } sort(w+1,w+1+n); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+w[i]; dfs(1,1); cout<<ans; }

详情