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

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

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

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

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

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

you solved it?

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

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

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

I made it complicated. Good approach✌

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

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

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

1 Like

Do u wanna solve same type of question one more ?

would love to send link please

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

thanks again

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

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

Bro just take a graph and dry run.