【每日一题】4月1日题目精讲 树型dp

题目描述

Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权
​现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。

输入描述:

第一行三个整数 N,M,S，意义如「题目描述」所述。
接下来 M 行，每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边。

输出描述:

一个整数表示答案。

示例1

4 3 1
1 2 1
1 3 1
1 4 1

输出

3

说明

需要使得点 2,3,4 不能到达点 1，显然只能删除所有的边，答案为 3

示例2

4 3 1
1 2 3
2 3 1
3 4 2

输出

1

说明

需要使得点 4 不能到达点 1，显然删除边 是最优的。

备注:

，保证答案在 C++ long long 范围内。

题解

注意备注里面说：M=N-1（读题一定要看备注！），题面说是个无向联通图，这就告诉我们实际上这就是一棵树。而题目中说到的度数为1的点实际上就的叶子节点。

现在问题就变成了：在以S为根的树上删掉权值和尽量小的一些边使得根和每一个叶子节点都不连通。

这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。

不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的，我们的原问题是以S为根的子树删掉权值和尽量小的一些边使得S和每一个叶子节点都不连通，那么子问题也很简单，就是求以x为根的子树删掉一些边使得S和x的子树上每个叶子节点都不连通。

要想在考虑x这个点的子树的时候就实现子树上每个叶子都和S不连通，那么有两种情况：

• 把x和他的所有儿子断开
• 在x的子树上去把所有叶子节点都断开。

如果我们用f[x]表示x的子树上的所有叶子和根断开的最小代价的话，(y是x的儿子，dis[x] [y]是x到y的边长)。 dfs在返回的时候维护这些值就好。

注意f的初值——所有的叶子节点f值应为一个极大值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,LL> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=100010;
vector<PII> g[N];
LL f[N];
int n,m,s;

void dfs(int u,int fa)
{
    bool leaf=1;
    for(int i=0;i<g[u].size();i++)
    {
        int j=g[u][i].first;
        LL w=g[u][i].second;
        if(j == fa) continue;
        leaf=0;
        dfs(j,u);
        f[u]+=min(f[j],w);
    }

    if(leaf) f[u]=IINF;
}

int main()
{
    cin>>n>>m>>s;

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }

    dfs(s,-1);

    cout<<f[s]<<endl;
    // system("pause");
}