Break And Fix The Tree CodeChef Solution – Code Drive solution

About Break And Fix The Tree CodeChef Solution

  • This is a coding contest based on algorithms, data structures, and problem-solving.
  • Organizer: The contest is hosted by NIT Trichy.
  • Prizes: NA
  • Registrations for prizes: NA

Problem: Break And Fix The Tree CodeChef Solution

Chef is playing a game, and to win the prize, he must complete it. But he is busy arranging meals for the vortex party, so he asked you the play the game in his place. The game is as below:

You are given a rooted tree of size NN rooted at node 11, where each node ii has a value ViVi assigned to it. Define PuPu as the parent of node uu. You have to perform queries of the following type on the tree:

  1. 1XW1XW: Break the edge between node XX and PXPX in the tree, and attach XX as a child of WW (note that this means PX=WPX=W after this operation). It is guaranteed that XX is a leaf node of the tree.
  2. 2XK2XK: Change the value on node XX to KK (i.e. assign VX←KVX←K).
  3. 3XY3XY: Calculate the sum of values of nodes on the path from XX to YY.

Note that the queries are accumulative, meaning the changes made in each query is persisted for the following queries.

Input Format

  • The first line of the input contains an integer NN – the number of nodes in the tree.
  • The next line contains N−1N−1 space-separated integers P2,P3,…,PNP2,P3,…,PN – the parents node of 22 to NN.
  • The next line contains NN space-separated integers V1,V2,…,VNV1,V2,…,VN – the initial values of the nodes.
  • The next line contains an integer QQ – the number of queries.
  • Each of the next QQ lines contains a query as described in the statement.

Output Format

For each query of type 33, output on a new line the sum of values of nodes on the path from XX to YY.

Constraints

  • 2≤N≤1052≤N≤105
  • 1≤Pi≤N1≤Pi≤N
  • −109≤Vi≤109−109≤Vi≤109
  • 1≤Q≤1051≤Q≤105
  • 1≤X,Y,W≤N1≤X,Y,W≤N
  • X≠WX≠W
  • −109≤K≤109−109≤K≤109

Sample Input 1 

5
1 1 2 2
1 2 3 4 5
6
3 4 5
1 4 3
1 5 3
1 2 4
2 4 10
3 2 5

Sample Output 1 

11
20

Explanation

  • Initially, the tree is
image original
  • For first query, the path followed is 4→2→54→2→5. Therefore the sum of values is 4+2+5=114+2+5=11.
  • After updating the tree according to second query, it becomes
image
  • After updating the tree according to third query, it becomesimage
  • After updating the tree according to fourth query, it becomesimage
  • After updating the tree according to fifth query, it becomesimage
  • The path for the sixth query is 2→4→3→52→4→3→5. Therefore the sum of values is 2+10+3+5=202+10+3+5=20.

Solution : Break And Fix The Tree CodeChef Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int>> adj;
vector<ll> sz,wt;
ll dfs(int u,int p)
{
    sz[u]=wt[u];
    for(auto v : adj[u])
    {
        if(v!=p)
        {
            sz[u]+=dfs(v,u);
        }
    }
    return sz[u];

}
pair<ll,int> count(int u,int p,ll x)
{
    if(sz[u]<=x) return {sz[u],0};
  //  if(adj[u].size()==1 && p!=-1 && sz[u]> x) return {sz[u],2e4+1};
    int cnt=0;
    vector<pair<ll,int>> vec;
    for(auto v : adj[u])
    {
        if(v==p) continue;
        if(sz[v]>x)
        {
           pair<ll,int> d = count(v,u,x);
           cnt+=d.second;
          // if(d.first> x) return {sz[u],2e4+1};
           vec.push_back({d.first,v});
        }
        else
        vec.push_back({sz[v],v});
    }
    sort(vec.begin(),vec.end());
    ll sum=wt[u];
    for(int i=0;i<vec.size();i++)
    {
        if(sum+vec[i].first<=x) sum+=vec[i].first;
        else
        {
            cnt+=vec.size()-i;
            break;
        }
    }
  //  if(sum<=x)
    return {sum,cnt};
   // else return {sum,2e4+1};
}
int main()
{
    int n,k;
    cin>>n>>k;
   // vector<int> wt(n);
    wt.resize(n);
    sz.resize(n);
    ll l=0;
    ll r=0;
    for(int i=0;i<n;i++)
    {
        cin>>wt[i];
        l=max(l,wt[i]);
        r+=wt[i];
    }
    adj.resize(n);
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,-1);
    ll ans=-1;
   // cout<<l<<" "<<r<<endl;;
    while(l<=r)
    {
        ll mid = l+(r-l)/2;
        pair<ll,int> val=count(0,-1,mid);
        //cout<<mid<<" "<<val.second<<"\n";
        if(val.second<=k-1)
        {
            ans=mid;
            r=mid-1;
            
        }
        else l=mid+1;

    }
    cout<<ans<<endl;
    
}

Contest Details:

  • This is an External Rated Contest.
  • Duration: 3 Hours
  • Start time: 30th December 2021, 20:00 hrs IST
  • End time: 30th December 2021, 23:00 hrs IST
    You may check your timezone here.
  • This contest is rated only for Division 2 and Division 3 users. Division 1 users can participate unofficially in this contest.

Get More CodeChef Solution >>

Substring Minimum Function FizzBuzz Solution

Magical Planks Fizzbuzz Solution

Favourite String of Chef CodeChef Solution

Sum this up Code Chef Solution

Game between friends CodeChef Solution

Leave a Reply

error: Content is protected !!