DP on tree

Template problem: rebuilding roads

https://www.luogu.com.cn/problem/P1272

Meaning:

There are n points and n-1 edges. Finding at least how many edges to remove will separate a subtree containing P points from other nodes.

analysis:

By reading the question, we can know that this tree contains root nodes and is acyclic, so we can think from top to bottom or from bottom to top.

We can maintain a two-dimensional array dp [i] [j], I represents the root node of the subtree, j represents the number of nodes of the subtree, and dp [i] [j] represents the number of edges to be deleted to obtain the subtree with the number of nodes j and the root node I.

For the root node s of a subtree, the subtree contains n points. We use c(vi) to represent the number of points reserved in the subtree rooted by the child node vi of S.

So there
n = ∑ c ( v i ) + 1 　 － － － － － － － － － － － １ n = \sum c(v_i)+1　－－－－－－－－－－－１ n=∑c(vi​)+1　－－－－－－－－－－－１
The following plus 1 is because the root node is included.

At the same time, we use d(vi) to represent the number of edges deleted in the subtree rooted by the sub node vi of s

So there
d p [ s ] [ n ] = ∑ d ( v i ) 　 － － － － － － － － ２ dp[s][n] = \sum d(v_i)　－－－－－－－－２ dp[s][n]=∑d(vi​)　－－－－－－－－２
Therefore, what we need to do is to find a way to minimize formula 2 while satisfying Formula 1 on the root node s of the subtree.

This is similar to the knapsack problem. A backpack filled with a certain capacity maximizes the value. Then, by analogy with n objects in a knapsack, there are n nodes, that is, n subtrees, n for each subtree_ I contains k child nodes.

So the knapsack problem is dp[i] [j]

Similarly, n_ For subtrees with I nodes as roots, there are DP [n_i] [i] [J], n_ I represents the number of the root node, I represents the ith subtree of the root node, and j represents n_ I is the subtree of the node, and j points are reserved on the subtree of the ith node, dp[n_i] [i] [j] indicates how many edges are deleted.

In order to be consistent with dp [i] [j] above, dp[i] [k] [j] is uniformly used here. I represents the number of the root node, K represents the kth subtree under the root node, and j represents that J nodes are reserved under the kth subtree. dp[i] [k] [j] indicates how many edges have been deleted.

Then the state transition equation can be written:
d p [ i ] [ k ] [ j ] = m i n ( d p [ i ] [ k − 1 ] [ j ] + 1 , d p [ i ] [ k − 1 ] [ j − s k ] + d p [ k ] [ s k ] ) dp[i][k][j] = min(dp[i][k-1][j]+1 , dp[i][k-1][j-s_k] + dp[k][s_k]) dp[i][k][j]=min(dp[i][k−1][j]+1,dp[i][k−1][j−sk​]+dp[k][sk​])
Explanation:

dp[i] [k] [j]

For the subtree with i as the root node, it retains j points on the subtree generated by the k-th child node and the number of edges to be deleted

dp[i] [k-1] [j]

For the subtree with i as the root node, it retains j points and the number of edges to be deleted on the subtree generated by the k-th child node.

Why add 1 here? Compared with knapsack problem, knapsack problem dp[i] [j] can be equal to dp[i-1] [j], which means I don't take the ith item. It also means that I don't reserve nodes from the kth subtree, so I have to disconnect the edge between I and k, so I want to add 1

dp[i] [k-1] [j-s_k] + dp[k] [s_k]

S here_ K is an enumerator, which generally means that I take j-s from the k-1 subtree_ K points and take s from the k-th subtree_ K points make up j points. The number of deleted edges is also rounded out from both sides.

At the same time, we can see from the equation that the state of the ith subtree should be transferred from its subtree, so the whole tree should be from low to top dp.

Core code

void dfs(int now ,int fa){
	sum[now] = 1 ,dp[now][0][1] = 0;
	//sum[now] indicates the number of nodes in the subtree. At first, there is only the root node, so there is one
	//dp[now][0][1] represents the initial quantity of the dp process. It has no practical significance. It is a process quantity. It is not the same as the number of edges to be deleted by retaining only one point. This should be dp [now] [cnt[now] [1], where cnt[now] represents the number of child nodes of the current node
	int k = 1;//The k th subtree
	for(int i=0;i<edge[now].size();i++){
		int to = edge[now][i];
		if(to==fa)continue;
		dfs(to,now);
		sum[now]+=sum[to]; //Number of nodes of cumulative subtree
		for(int j = sum[now];j>0;j--){
			dp[i][k][j] = dp[i][k-1][j]+1;//State transition former
			for(int h =0;h<=min(sum[to],j-1);h++){
				dp[i][k][j] = min(dp[i][k][j] , dp[i][k-1][j-h] +dp[to][cnt[to]][h]);
				//State transition the latter
			}
		}
		k++;
	}
}

Optimization part

Since dp on the tree can be compared with knapsack problem, one dimension can be reduced like knapsack. Here, the second dimension can be reduced by rolling array

void dfs(int now, int p)
{
  sum[now] = 1, dp[now][1] = 0;
  for (int i = 0; i < ve[now].size(); i++)
  {
    int to = ve[now][i];
    if (to == p)
      continue;
    dfs2(to, now);
    // debug(now);
    sum[now] += sum[to];
    // debug(sum[now]);
    for (int j = sum[now]; j >0; j--)
    {
      dp[now][j]++;//k was rolled off
      for (int k = 1; k <= min(sum[to], j - 1); k++)
      {
        dp[now][j] = min(dp[now][j], dp[now][j - k] + dp[to][k]);
      }
    }
  }
}

Complete code

#include <algorithm>
#include <cstring>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " :" << x << endl;
const int maxn = 1e3;
const int INF = 1e9;
int n, p;
vector<int> ve[maxn];
int ru[maxn];
int sum[maxn];
int dp[maxn][maxn];

void dfs2(int now, int p)
{
  sum[now] = 1, dp[now][1] = 0;
  for (int i = 0; i < ve[now].size(); i++)
  {
    int to = ve[now][i];
    if (to == p)
      continue;
    dfs2(to, now);
    // debug(now);
    sum[now] += sum[to];
    // debug(sum[now]);
    for (int j = sum[now]; j >0; j--)
    {
      dp[now][j]++;
      for (int k = 1; k <= min(sum[to], j - 1); k++)
      {
        dp[now][j] = min(dp[now][j], dp[now][j - k] + dp[to][k]);
      }
    }
  }
}
int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int _ = 1;
  //cin >> _;
  while (_--)
  {

    cin >> n >> p;
    int t1, t2;
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        dp[i][j] = INF;
      }
    }
    for (int i = 1; i < n; i++)
    {
      cin >> t1 >> t2;
      ve[t1].push_back(t2);
      ve[t2].push_back(t1);
      ru[t2]++;
    }
    int root = 0;
    for (int i = 1; i <= n; i++)
    {
      if (!ru[i])
      {
        root = i;
        break;
      }
    }
    // dfs1(1, 0);
    // init();
    dfs2(1, 0);
    int ans = dp[1][p];
    for (int i = 2; i <= n; i++)
    {
      ans = min(ans, dp[i][p] + 1);
    }
    cout << ans << endl;
  }
}