Delete Edge!

• Time : $O(v + e)$
• Space : $O(v + e)$

#include <bits/stdc++.h>
long long mod = 1e9 + 7;
long long dfs1(vector<int>& A, vector<long long>& B, int u, int par, vector<vector<long long>>& adj) {
    B[u] += A[u];
    for(auto v : adj[u]) {
        if(v == par) continue;
        B[u] += dfs1(A,B,v,u,adj);
    }
    return B[u];
}

int Solution::deleteEdge(vector<int> &A, vector<vector<int> > &B) {
    vector<long long> sum(A.size());
    vector<vector<long long>> adj(A.size());
    for(int i = 0; i < B.size(); i++) {
        auto u = B[i][0], v = B[i][1];
        u -= 1, v -= 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(A,sum,0,-1,adj);
    long long res = 0, every = accumulate(begin(A), end(A), 0ll);
    for(int i = 0; i < sum.size(); i++) {
        res = max(res, (every - sum[i]) * sum[i]);
    }
    return res % mod;
}