Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.0 kB
7
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

long long res, ans;

vector<long long> sum;
vector<vector<int>> g;

void dfs(int v, int p = -1, int h = 0,int a[]) {
	res += h * 1ll * a[v];
	sum[v] = a[v];
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs(to, v, h + 1);
		sum[v] += sum[to];
	}
}

void go(int v, int p = -1) {
	ans = max(ans, res);
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		
		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		sum[to] -= sum[v];
		res -= sum[v];
		sum[v] += sum[to];
		res += sum[to];
	}
}

int maxbeauty(int tree_nodes,int tree_from[],int tree_to[],int a[tree_nodes])
{

int tree_edges=tree_from.size()/tree_from[0].size();

int n=tree_edges;

for (int i = 0; i < n - 1; ++i) {

		g[tree_from[i]].push_back(tree_to[i]);
		g[tree_to[i]].push_back(tree_from[i]);
	}
   
   dfs(0,&a);
   go(0);
   return ans;
}

int main()
{
cout<<maxbeauty(2,{1},{2},{3,4});

}