CAC2022 Editorial

editorial
, ,
1

PROBLEM LINK:

Tree and its components

Author: dragno99
Editorialist: dragno99

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

Given a tree with N nodes, you can perform two types of operation

  • Break an edge with a cost of its weight
  • Change the colour of any node at a cost of C_{i}

For each query, you have to find the minimum cost of obtaining a connected connected component of a given tree having size equal to x and consisting of exactly k coloured nodes by performing any type of operation , any number of times.

Prerequisites:

  • DFS , DP on TREE

EXPLANATION:

This problem has a straight forward dp solution, first we will apply a dfs on any node assuming it to be a root node, now our dfs function will return a 2d vector dp[i][j] , which means if we consider only this subtree whose parent is root node, then the minimum cost of obtaining a connected component is dp[i][j] such that it contains exactly i nodes with root and has exactly j coloured nodes.
Now rest of the part is merging the current root with its parents. Now if we consider current root with its parent while merging then extra cost will not add but if we break this edge then we have to add its breaking cost.
You can check implementation for better understanding, in implementation the two loop for merging two different subtree seems like overall solution will take N^3 * 10 * 10 time but in reality, its time complexity will be N^2 * 10 * 10 which can fits in constraints.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define eb emplace_back
#define inf 100000000000000
#define forr(i,n) for(int i=0;i<n;i++)

using namespace std;


const int N = 1e3 + 10 , K = 11;
vector<pair<int,int>> g[N];
vector<int> sub ,a , c;
vector<vector<long long>> ans;

vector<vector<long long>> dfs(int node,int par,int p_cost){
   vector<vector<long long>> dp(2,vector<long long>(K,inf));
   sub[node] = 1;
   if(a[node]){
       dp[1][0] = c[node];
       dp[1][1] = 0;
   }
   else{
       dp[1][0] = 0;
       dp[1][1] = c[node];
   }
   for(auto &[child,cost]: g[node]){
       if(child != par){
           auto curr = dfs(child , node , cost);
           vector<vector<long long>> new_dp(sub[node] + sub[child] + 1 , vector<long long>(K,INT_MAX/10) );
           for(int use1=0;use1<K;use1++){
               for(int use2=0;use2 + use1 < K;use2++){
                   for(int i=1;i<=sub[node];i++){
                       for(int j=1;j<=sub[child];j++){ 
                           // when we do not delete this edge
                           new_dp[i + j][ use1 + use2 ] = min(new_dp[i + j][use1+use2] , dp[i][use1] + curr[j][use2]);
                       }
                       // when we delete this edge
                       new_dp[i][use1] = min(new_dp[i][use1] , dp[i][use1] + cost);
                   }
               }
           }
           sub[node] += sub[child];
           dp.swap(new_dp);
       }
   }
   for(int use=0;use<K;use++){
       for(int i=0;i<=sub[node];i++){
           ans[i][use] = min(ans[i][use] , dp[i][use] + p_cost );
       }
   }
   return dp;
}



void init(int n){
   for(int i=0;i<=n;i++){
       g[i].clear();
   }
   ans.assign(n+1,vector<long long>(11, inf));
   sub.assign(n+1,0);
   a.assign(n+1,0);
   c.assign(n+1,0);
}


int main(){
   int n , q; cin >> n >> q;
   
   init(n);

   forr(i,n-1){
       int x,y , w; cin >> x >> y >> w;
       g[x].eb(y,w);
       g[y].eb(x,w);
   }

   for(int i=1;i<=n;i++){
       cin >> a[i];
   }
   for(int i=1;i<=n;i++){
       cin >> c[i];
   }
   

   dfs(1,1,0);

   while(q--){
       int x , k; cin >> x >> k;

       cout << ans[x][k] << endl;
   }

}