# HackerEarth Sum of Sums problem solution

In this HackerEarth Sum of Sums problem solution Given a undirected tree containing N nodes where ith node has value a(i). Let us define cost of the tree as C, where
C = Summation(i=1, N) f(i)
f(i) = Summation(j) g(j); where j belongs to subtree of i
g(j) = Summation(k) a(k); where k belongs t subtree of j
Find a root of the tree such that the cost of the tree is minimum.

## HackerEarth Sum of Sums problem solution.

`#include<bits/stdc++.h>using namespace std;#define N 100009long long a[N],g[N],h[N],ans,ans2,mx;vector<int> G[N];void dfs1(int u,int p){  h[u]=a[u];  g[u]=0;  for(int v:G[u]){    if(v==p)      continue;    dfs1(v,u);    h[u]+=h[v];    g[u]+=g[v];  }  g[u]+=h[u];//  cout<<"u : "<<u<<" "<<" , h[u] : "<<h[u]<<" , g[u] : "<<g[u]<<endl;  return ;}void dfs2(int u,int p){  //cout<<"u : "<<u<<" "<<" , ans : "<<ans<<endl;  if (mx > ans) {    mx = ans;    ans2 = u;  }  else if (mx == ans && ans2 > u)    ans2 = u;  for(int v:G[u]){    if(v==p)      continue;    g[u]-=g[v];ans-=g[v];    g[u]-=h[u];ans-=h[u];    h[u]-=h[v];    g[u]+=h[u];ans+=h[u];    g[v]+=g[u];ans+=g[u];    g[v]-=h[v];ans-=h[v];    h[v]+=h[u];    g[v]+=h[v];ans+=h[v];    dfs2(v,u);    g[v]-=h[v];ans-=h[v];    h[v]-=h[u];    g[v]+=h[v];ans+=h[v];    g[v]-=g[u];ans-=g[u];    g[u]-=h[u];ans-=h[u];    h[u]+=h[v];    g[u]+=h[u];ans+=h[u];    g[u]+=g[v];ans+=g[v];  }  return ;}int main(){  //freopen("in00.txt", "r", stdin);  //freopen("out14.txt", "w", stdout);  ios_base::sync_with_stdio(false);cin.tie(NULL);  int n;  cin>>n;  for(int i=0;i<n;i++){    cin>>a[i];  }  for(int i=0;i<n-1;i++){    int u,v;    cin>>u>>v;    u--;v--;    G[u].push_back(v);    G[v].push_back(u);  }  dfs1(0,-1);  ans=0;  for(int i=0;i<n;i++){    ans+=g[i];  }  mx=LLONG_MAX;  ans2=-1;  dfs2(0,-1);  cout<<ans2+1<<" "<<mx<<endl;  return 0;}`

### Second solution

`#include <string>#include <vector>#include <map>#include <list>#include <iterator>#include <cassert>#include <set>#include <queue>#include <iostream>#include <sstream>#include <stack>#include <deque>#include <cmath>#include <memory.h>#include <cstdlib>#include <cstdio>#include <cctype>#include <algorithm>#include <utility>#include <time.h>#include <complex>using namespace std;#define FOR(i, a, b) for(int i=(a);i<(b);i++)#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)#define FILL(A,value) memset(A,value,sizeof(A))#define ALL(V) V.begin(), V.end()#define SZ(V) (int)V.size()#define PB push_back#define MP make_pair#define Pi 3.14159265358979#define x0 ikjnrmthklmnt#define y0 lkrjhkltr#define y1 ewrgrgtypedef long long Int;typedef unsigned long long UInt;typedef vector<int> VI;typedef pair<int, int> PII;typedef pair<Int, Int> PLL;typedef pair<double, double> PDD;typedef complex<double> base;const int INF = 1000000000;const int BASE = 1000000007;const int MAX = 100007;const int ADD = 1000000;const int MOD = 1000000007;const int CNT = 800;const double eps = 1e-8;VI G[MAX];Int f[MAX];Int g[MAX];int a[MAX];void dfs(int v, int p){  g[v] = a[v];  FOR(i,0,SZ(G[v]))  {    int to = G[v][i];    if (to == p) continue;    dfs(to, v);    g[v] += g[to];    f[v] += f[to];  }  f[v] += g[v];}Int cur, M , id;void dfs2(int v, int p){  //cout << v << ' ' << cur << endl;  if (cur < M)  {    M = cur;    id = v + 1;  }  FOR(i,0,SZ(G[v]))  {    int to = G[v][i];    if (to == p) continue;    Int cc = cur;    Int ffv = f[v];    Int fft = f[to];    Int ggv = g[v];    Int ggt = g[to];    cur -= f[v];    cur -= f[to];    f[v] -= f[to];    f[to] -= g[to];    f[v] -= g[v];    g[v] -= g[to];    f[v] += g[v];    f[to] += f[v];    g[to] += g[v];    f[to] += g[to];    cur += f[v];    cur += f[to];    //cout << f[v] << ' ' << g[v] << ' ' << f[to] << ' ' << g[to] << endl;    dfs2(to, v);    cur = cc;    f[v] = ffv;    f[to] = fft;    g[v] = ggv;    g[to] = ggt;  }}int main(){    //freopen("in.txt", "r", stdin);    //freopen("distance.in",  "r", stdin);    //freopen("distance.out", "w", stdout);    //freopen("out.txt" , "w" , stdout);  int n;  cin >> n;  assert(n >= 1 && n <= 100000);  FOR(i,0,n)  {    scanf("%d", &a[i]);    assert(a[i] >= 1 && a[i] <= 1000000);  }  FOR(i,0,n - 1)  {    int a , b;    scanf("%d%d" , &a , &b);    assert(a >= 1 && a <= n);    assert(b >= 1 && b <= n);    -- a;    -- b;    G[a].push_back(b);    G[b].push_back(a);  }  dfs(0,-1);  FOR(i,0,n)  {    assert(f[i] >= 1);  }  cur = 0;  FOR(i,0,n)  {    cur += f[i];  }  M = cur;  id = 1;  dfs2(0,-1);  cout << id << ' ' << M << endl;    return 0;}`