# Minimize the value (hackerearth)

https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/minimize-the-magic-05a3986c/
unknown
c_cpp
7 months ago
1.6 kB
5
Indexable
Never
```#include<bits/stdc++.h>

using namespace std;

#define ll long long

void dfs(int u, vector< vector<int> > &g, vector<bool> &visited, vector<int> &level){

visited[u]=true;

for(int i=0;i<g[u].size();i++){
int v=g[u][i];

if(visited[v]==false){
level[v]=level[u]+1;
dfs(v,g,visited,level);
}
}

return;
}

void dfs2(int u, vector< vector<int> > &g, vector<bool> &visited, vector<ll> &val){
visited[u]=true;

for(int i=0;i<g[u].size();i++){
int v= g[u][i];

if(visited[v]==false){
dfs2(v,g,visited,val);
val[u]+=val[v];
}
}
return;
}

void solve()
{
int n,x;
cin>>n>>x;

vector< vector<int> > g(n+2, vector<int>() );
vector<bool> visited(n+2, false);
vector<ll> val(n+2);

vector<int>level(n+1);

for(int i=1;i<n+1;i++){
level[i]=0;
}

for(int i=1;i<n+1;i++){
cin>>val[i];
}

val[n+1]=x;

for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;

g[u].push_back(v);
g[v].push_back(u);
}

dfs(1,g,visited,level);

int xParent = 0;
level[xParent]=n+10;

if(g[1].size()<2){
xParent=1;
}

for(int i=2;i<n+1;i++){
if((g[i].size()<3) && level[xParent]>level[i]){
xParent=i;
}
}

g[xParent].push_back(n+1);

for(int i=0;i<n+2;i++){
visited[i]=false;
}

dfs2(1, g, visited,val);

ll ans=0;

for(int i=1;i<n+2;i++){
ans+=val[i];
}

cout<<ans<<endl;

return;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

solve();

return 0;
}```