long maxBeauty(int tree_nodes, vector<int> tree_from, vector<int> tree_to, vector<int> a) {
    vector<vector<int>> g(tree_nodes+1);
    for(int i=0;i<tree_nodes-1;++i) {
        int x = tree_from[i], y = tree_to[i];
        g[x].push_back(y), g[y].push_back(x);
    }
    vector<long> sum(tree_nodes+1), dp(tree_nodes+1);
    function<void(int,int)> dfs = [&](int s,int p) {
        sum[s] = a[s-1];
        for(auto &j:g[s]) {
            if(j == p) {
                continue;
            }
            dfs(j, s);
            sum[s] += sum[j];
            dp[s] += dp[j];
            dp[s] += sum[j];
        }
    };
    dfs(1, 0);
    long ans = 0;
    function<void(int,int)> dfs2 = [&](int s,int p) {
        ans = max(ans, dp[s]);
        for(auto &j:g[s]) {
            if(j == p) {
                continue;
            }
            dp[j] += dp[s] - (dp[j] + sum[j]) + sum[1] - sum[j];
            dfs2(j, s);
        }
    };
    dfs2(1, 0);
    return ans;
}