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

help
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

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?

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

“Problem - E1 - Codeforces”

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?

21

Bro just take a graph and dry run.