题目

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

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

输出描述：
一个整数表示答案。

解析

这道题是一道简单的树形dp，只是我对树形dp（实则是对dp）不太熟，所以没想到求解方法。
  • 所以开头还是那句话：动态规划的基础就是递推。

树形dp：
  1. 想要求解这道题，我们先要读懂题目的意思：我们要用最少的代价，使得当前根节点和所有叶子节点不相连（看题很重要，一开始我没发现是树）。
  2. 然后到这里，我们就要想一下该怎么递推，该怎么把大问题分解成等同的小问题（我就是在这卡到了）。
  3. 所有在这里，根据我们要做的事情：断开节点：我们应该想到以某一u（节点）为根节点的树对一条分支有两种断开方法。
    <1>断开自己和某一v（子节点）之间的关系。<2>断开子节点v的所有子节点（一定是断开所有子节点，因为树的每一条分支最终一定以叶节点结束）。
  4. 所以我们就能得到转移方程：（w表示u到某一分支的权值）。
  • 补充一句邓老师告诉我的话：树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。

打代码哦：
  1. 前向星保存树形关系。
  2. dfs进行优先遍历。（上面树形dp讲了详细方法）
  3. 其他重要的就是一点点操作顺序了吧，看代码~

AC代码 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
    int v, w, next;
} edge[MAX << 1];
ll f[MAX];
//全局变量区

template<class T>inline void read(T& res);
void add_edge(int u, int v, int w);
void dfs(int u, int fa);
//函数预定义区

int main() {
    int N, M, S; read(N); read(M); read(S);
    tot = 0; memset(head,  0,  sizeof  head);
    for (int i = 1; i <= M; i++) {
        int u, v, w; read(u); read(v); read(w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
        memset(f, 0, sizeof f);
    dfs(S, 0);
    printf("%lld", f[S]);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void add_edge(int u, int v, int w) {
    tot++;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    int flag = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        int w = edge[i].w;
        if (fa == v) continue;
        flag = 1;
        dfs(v, u);
        f[u] += min(f[v], (ll)w);
    }
    if (!flag) f[u] = INF;
}
//函数区