You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. Each node has a value; let's denote the value of node i by Ai.
You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.
Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.
#i need the code in c program or puthon 3.6
You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.
Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.
#i need the code in c program or puthon 3.6
Add an Answer
More Questions From This User See All
Answers & Comments
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<limits>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
vector<int>v[100001];
ll val[100001];
ll sum[100001];
int nodesum(ll root,bool* visited)
{
ll temp=val[root];
visited[root]=true;
for(ll j=0;j<v[root].size();j++)
{
if(!visited[v[root][j]])
{
temp+=nodesum(v[root][j],visited);
}
}
return sum[root]=temp;
}
void dfs(ll i,bool* vis,ll k)
{
vis[i]=true;
ll temp=val[i];
for(int j=0;j<v[i].size();j++)
{
if(!vis[v[i][j]])
{
dfs(v[i][j],vis,k);
temp+=max(sum[v[i][j]],-k);
}
}
sum[i]=temp;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++)
cin>>val[i];
for(ll i=0;i<=n;i++)
{
v[i].clear();
}
for(ll i=1;i<n;i++)
{
ll a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
bool visited[n+1]{};
ll ans=nodesum(1,visited);
bool vis[n+1]{};
dfs(1,vis,k);
ans=max(sum[1],-k);
cout<<ans<<endl;
}
}