Was solving this problem but dont know how to comeup with recursive function for this tree problem

help
#1

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.

The contest is closed

#2

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” :)).

#3

bro the contest is closed may be you might not get the accesss to the question anyways am sharing the link

https://www.scaler.com/test/129e94a0ba/?signature=BAhpAw%2BUDA%3D%3D--b083e1e266d0d05b117f78670591a4b448a8c52d#/problem_1

#4

as i said the test is no longer available … its just i copied the questions which i didnt solved

#5

also it is the original statement ( i havent rendered even a single word)

#6

Yes the contest is over. It was yesterday’s Scalar hiring challenge from 6.30-9.30 pm and this was the first problem

1 Like
#7

you solved it?

Scaler Question
#8

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

#9

more simpler -

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

@ssjgz @yolok

1 Like
#10

5 4(edges)
1 3 100
1 5 10
2 3 123
5 4 55

                         1
                        / \
                  (100)/   \ (10)
                      /     \
                     3       5
                    /        \
             (123) /          \ (55)
                  /            \
                 2              4

after DFS weight of egdes passed to just below node as they contribute in path

                         1(0)[4]
                        / \
                       /   \ 
                      /     \
                (100)3[2]   5(10)[2]
                    /        \
                   /          \ 
                  /            \
             (123)2 [1]        4(55)[1]

[] denotes the subtree size of node
() denotes the value of node

1 Like
#11

I made it complicated. Good approach✌

#12

thanks bro really helped alot learnt something new.Just one doubt like when can the pq.top() be negative??

#13

suppose all weight is -ve so why we need to pop , bcz if we pop we increases the sum but we have to minimize it .

or let say given C is 5 but after pop two element (now C is 3 ) the values are -ve in priority queue then no need to pop

12
5
-3
-2
-1

C = 5
pop 2 times
-3
-2
-1

(C is 3 now)

total sum -3-2-1 = -6

but if we pop -3 too then sum is -2-1 = -3 which is more but we have to minimize.

Hope u understand.

1 Like
#14

nice explanation bro .GOT IT and saying it again that was really helpful

1 Like
#15

Do u wanna solve same type of question one more ?

#16

would love to send link please

#17

“https://codeforces.com/contest/1399/problem/E1”

#18

thanks again

#19

Do you remember the constraints for B[ i ][ 1 ] ?

#20

Can anyone please explain, when the code in the else statement will be executed?