树形dp初探

此题目的意思就是现在有以s节点为根节点的一棵树，要求断掉一些边， 使得叶子节点无法到达根节点（在
一个树中， 只有一个度的节点只有叶子节点，或者单链式的树(如样例2)）
单链式的树根节点和叶子节点都有且只有一个度，所以要特殊考虑一下

下面直接考虑树形dp做法

考虑一下研究总问题：以s为节点的子树断掉一些边，使得叶子节点无法到达根节点

那么在dp做法下， 肯定要考虑子问题 ， 那么总问题的子问题肯定和它的孩子节点有关

用dp[u] 表示以u为节点的子树断掉一些边， 使得叶子节点无法到达u节点

通常做法就是考虑s节点的孩子节点 ， 对于s节点来说

1、直接断掉一条到孩子节点v的边 ， 那么这个时候这个v这个孩子就不用考虑了(因为这个子树所有点都不能到达s节点了)

2、不断掉到孩子节点的v的边， 那么我就要考虑问题：

以v为节点的子树断掉一些边， 使得叶子节点无法到达v节点

第二个情况实际上也就是总问题的子问题

什么时候选择第一种情况 :

如果只考虑s节点，那么dp[s] = ??

对于s节点的孩子节点x 来说， 如果第一种情况比第二种情况优 ， 也就是dis(s , x) > dp[x]

那么就选择第一种情况 ， 否则的就选择第二种情况

那么用dp的思想也就是当前节点u的孩子节点的贡献就是 min(dp[v] , dis(u , v))

还因为u节点不止一个孩子节点， 那么就是dp[u] += min(dp[v] , dis(u , v))

所谓的记忆化搜索(蒟蒻个人感觉来说) 就是搜索过的东西，也就是搜索过的答案全部记录对应的位置 ， 如果搜索到了 已经被搜过的点 ，那么就直接返回 ， 否则的话，完成当前搜索步骤，在return的时候，同时记录相应的答案

树形dp一般都是先对于当前节点直接搜索， 然后在按照dp[u] += min(dis(u , v) , dp[v]) 计算贡献 ， 因为他要从当前节点搜到叶子节点， 然后返回的时候在将贡献计算

我才接触dp没多久

树形dp

#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
typedef long long ll ;
vector<pair<int , ll>> v[N] ;
int n , m , s ;
ll dp[N] ;
void dfs(int u , int fa)
{
  if(v[u].size() == 1 && u != s )
   {
     dp[u] = 0x3f3f3f3f ; 
// 这个要特殊处理， 因为单链式的叶子节点和根节点都有1个度
// 因为这个节点肯定是叶子节点 ， 然后呢返回上一层就是它的父亲节点
// dp[fa] += min(dp[u] , dis(u , fa)) , 
// 这个时候也就是边界， 肯定是选择dis(u , fa) ，
//将孩子节点直接断掉， 不考虑dp[u] ,所以将dp[u] 设置为正无穷
     return ;
   }
  for(auto x : v[u])
   {
     ll j = x.first , w = x.second ;
     if(j == fa) continue ;
     dfs(j , u) ;
     dp[u] += min(dp[j] , w) ;
   }
}
int main()
{
  cin >> n >> m >> s ;
  for(int i = 1; i <= m ;i ++)
   {
     int a , b , c ;
     cin >> a >> b>> c ;
     v[a].push_back({b , c}) ;
     v[b].push_back({a , c}) ;
   }
  dfs(s , 0) ;
  cout << dp[s] << endl ;
  return 0;
}

记忆化搜索 + 树形dp

#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
typedef long long ll ;
vector<pair<int , ll>> v[N] ;
int n , m , s ;
ll dp[N] ;
const ll INF = 1e18 ;
ll dfs(int u , int fa)
{
  if(dp[u]) return dp[u] ;
  if(v[u].size() == 1 && u != s) return INF ;
  ll ans = 0 ;
  for(auto x : v[u])
   {
     ll a = x.first , w = x.second ;
     if(a == fa) continue ;
     ans += min(dfs(a , u) , w) ;
   }
   return dp[u] = ans ;
}
int main()
{
  cin >> n >> m >> s ;
  for(int i = 1; i <= m ;i ++)
   {
     int a , b , c ;
     cin >> a >> b>> c ;
     v[a].push_back({b , c}) ;
     v[b].push_back({a , c}) ;
   }
  cout << dfs(s , 0) << endl ;
  return 0;
}