Description

The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

Problem link — http://poj.org/problem?id=1947

I am trying to understand the recurrence from below accepted solution but not able to understand few things. As per my understanding dp[i][j] = number of edges needs to be deleted for tree rooted at i having j nodes in that tree.

Doubt 1 Is it included root or only considers child

dp [ cur ][ j ] = min ( dp [ cur ][ j ] , dp [ v ] [ k ] + dp [ cur ][ j — k ] — 2 ); } dp[cur][j] when not considering child v dp [ v ] [ k ] + dp [ cur ][ j — k ] — 2 ) when considering child v and taking k nodes from it and j — k from the previous child nodes.

Doubt 2 why we are subtracting 2 when we include this child v rooted at v.

Accepted solution found from one blog(which does not have explanation to recurrence).

#include<stdio.h>
    #include<vector>
    #include<iostream>
    #define ll long long 
    #define pb push_back 
    #define pm make_pair 
    using  namespace  std ; 
    const  int  MAX  =  555 ; 
    const  int  INF  =  0x3f3f3f3f ; 
    int  dp [ MAX ][ MAX ] ; 
    // The minimum knife number 
    int  n  ,p;
    vector < int >  vv [ MAX ]; 
    void  dfs ( int  cur , int  rt ) { 
    int  up  =  vv [ cur ]. size (); 
    for ( int  i  =  0 ; i < up ; i ++ ) { 
        int  v  =  vv [ cur ][ i ]; 
        if ( v  ==  rt )continue ; 
        dfs ( v , cur ); 
        for ( int  j  =  p ; j > 1 ; j -- ) { 
        for ( int  k  =  1 ; k  <  j ; ++ k ) // divide into nodes under the subtree and itself 
        dp [ cur ][ j ] = min ( 
            dp [ cur ][ j ] , dp [ v ] [ k ] + dp [ cur ][ j - k ] - 2 ); 
        } 
    } 
    } 
    int  main () 
    { 
    cin >> n >> p ; 
    for ( int  a , b , i  =  1 ; i <= n - 1 ; i ++ ) { 
        cin>>a>>b;
        vv[ a ] .pb ( b ); 
        vv[ b ] .pb ( a ); 
    } 
    memset ( dp , INF , sizeof  dp ); 
    for ( int  i  =  1 ; i <= n ; i ++ ) dp [ i ] [ 1 ] =  vv [ i ]. size (); 
    dfs ( 1 , - 1); 
    int  ans  =  INF ; 
    for ( int  i = 1 ; i <= n ; i ++ ) ans = min ( dp [ i ][ p ], ans ); 
    cout  << ans  << endl ; 
    return  0 ; 
    }