CF #527 (Div. 3) F. Tree with Maximum Cost

F. Tree with Maximum Cost
제목 링크: Tree with Maximum Cost
제목
N 개의 점 을 가 진 나무 한 그루 를 드 리 겠 습 니 다. 점 마다 하나의 가중치 A [i] 가 있 습 니 다. 현재 MAX 값 을 점 v ＞ i = 1 n d i s t (i, v) * 8727 ° A [i] 로 정의 합 니 다. \ sum ^ n{i = 1} dist(i,v)*A[i] i=1∑n​dist(i,v)∗A[i]
이 값 이 최대 얼마 냐 고요?
데이터 범위: N < = 2 * 8727;A [ i ] < = 2 ∗ 1 0 5 N<=2*10^5; A[i] <= 2*10^5 N<=2∗105;A[i]<=2∗105
사고의 방향
이 점 이 하나 라 고 가정 하면 우 리 는 이 나 무 를 뿌리 로 하 는 나무 로 바 꿀 수 있다. 현재 각 점 대 일의 공헌 은 그의 깊이 * 그의 가치 이다. 그러면 우 리 는 이 나 무 를 그들의 중간 노드 로 분산 시 킬 수 있다. 그러면 각 점 이 대표 하 는 가 치 는 바로 그의 서브 나무의 합 이다.a n s = ∑ i = 1 n d i s t (i, v) ∗ A [i] = ∑ i = 1 n 점 i 의 모든 하위 노드 와 ans = \ \ sum ^ n{i = 1} dist(i,v)*A[i] = \sum ^n_{i = 1} {점 i 의 모든 하위 노드 와} ans = i = 1 ∑ n dist (i, v) ∗ A [i] = i = 1 ∑ n 점 i 의 모든 하위 노드 와 그 렇 기 때문에 우 리 는 먼저 dfs 를 진행 하여 각 점 의 하위 노드 의 합 을 찾 을 수 있 습 니 다. 점 에서 시작 하여 이동 할 때마다 O (1) O (1) O (1) O (1) 의 시간 만 필요 합 니 다.
전이 공식
코드

#include 
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<
#define pb push_back

typedef long long ll;
const int MAXN = (int)1e6+7;

int N;
ll A[MAXN];
ll sum[MAXN];
ll ans;
vector<int> G[MAXN];

void dfs(int u,int fa) {
    sum[u] = A[u];
    rep(i,0,G[u].size()-1) {
        int to = G[u][i];
        if (to == fa) continue;
        dfs(to,u);
        sum[u] += sum[to];
    }
}

void getMax(int u,int fa,ll now) {
    ans = max(ans,now);
    rep(i,0,G[u].size()-1) {
        int v = G[u][i];
        if (v == fa) continue;
        ll tmp = now + (sum[1]-sum[v]) - sum[v];
        getMax(to,u,tmp);
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> N;
    rep(i,1,N) cin >> A[i];
    rep(i,1,N-1) {
        int u,v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }

    dfs(1,-1);
    rep(i,2,N) ans += sum[i];
    getMax(1,-1,ans);
    cout << ans << endl;
}

/*
        
1.       ，
                ，                 ，        

*/