Untitled
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}); }