Given a tree containing A nodes rooted at node 1 .
Find the minimum value of the sum of Distance(1, i) where i varies from 1 to A using atmost C operations. In other words, find the minimum value of Distance(1, 1) + Distance(1, 2) + Distance(1, 3) … upto Distance(1, n) using atmost C operations.
In one operation you can change the weight of any edge to zero.
Nodes are connected by A-1 edges. Given an array B where B[i][0] (0-indexed) is connected to node B[i][1] with edge of weight B[i][2] .
NOTE:
Distance between node 1 and node i = Sum of weight of edges between them.
The global variables need to be cleared because the code will run for multiple test cases.
Return your answer modulo 109 + 7.
A = 5
B = [
[1, 2, 10]
[1, 3, 5]
[1, 4, 9]
[2, 5, 11]
]
C = 0
Given Tree:
1
/
2 3
/
4 5
Change the weight of edge connecting 1, 2 to 0.
Sum = Distance(1, 1) + Distance(1, 2) + Distance(1, 3) + Distance(1, 4) + Distance(1, 5).
= 0 + 0 + 5 + 3 + 14 = 22.
Can you please link to the actual Problem, so we can verify this? We’ll also get the correct Problem Statement (I doubt that they want the answer “modulo 116” :)).
Yes.
First find out the sum of all with all the given weights without making them 0. Now, find the total leaves of the subtree and calculate weight of edge*leaves. Sort them and run a dfs call
count subtree size of each node and multiply that with the given edge , after that remove min(given C , nodes untill the result is -ve) after that sum of all remaining values.
void dfs(lli src , vector<pii> adj[] , vbool &vis , vi &cnt_sub , vi &value_node)
{
vis[src]=1;
cnt_sub[src]=1;
for(auto xt : adj[src])
{
if(!vis[xt.F])
{
dfs(xt.F,adj , vis,cnt_sub,value_node);
cnt_sub[src] += cnt_sub[xt.F];
}
else
value_node[src] = xt.S;
}
}
int Solution::solve(int A, vector<vector<int> > &B, int C) {
vector<pii> adj[A+1];
loop(i,sz(B))
{
adj[B[i][0]].pb({B[i][1] , B[i][2]});
adj[B[i][1]].pb({B[i][0] , B[i][2]});
}
vbool vis(A+1 ,false);
vi cnt_sub(A+1,0) , value_node(A+1,0);
dfs(1,adj , vis , cnt_sub , value_node);
priority_queue<lli> pq;
lli total=0;
for(lli i=2;i<=A;i++)
{
total = cnt_sub[i]*value_node[i];
pq.push(total);
}
lli cnt =C;
while(cnt>0 and !pq.empty()){
if(pq.top() <0)
break;
pq.pop();
cnt--;
}
lli sumans = 0;
while(!pq.empty())
{
lli val = pq.top(); pq.pop();
sumans = ((sumans % mod + val%mod)%mod + mod)%mod;
}
return sumans%mod;
}