Rinne Loves Edges

树形DP
首先，中文题，就不再阐述题意了。
然后，具体怎么dp呢？首先不考虑树上，如果是一条序列上的话，肯定就是这条序列上的最小值了，现在其实实则变成了多条序列。
我们动态规划的主要思想就是在于，是割下面的点的代价要小，还是割目前的边要更好些，所以用dp[u]记录，u结点为子树的根结点的时候，断开它到它的叶子结点的最小代价是多少。
然后动态规划的过程就简单了：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, root, head[maxN], cnt;
struct Eddge
{
    int nex, to; ll val;
    Eddge(int a=-1, int b=0, ll c=0):nex(a), to(b), val(c) {}
}edge[maxN << 1];
inline void addEddge(int u, int v, ll w)
{
    edge[cnt] = Eddge(head[u], v, w);
    head[u] = cnt++;
}
inline void _add(int u, int v, ll w) { addEddge(u, v, w); addEddge(v, u, w); }
ll dp[maxN];
void dfs(int u, int fa)
{
    ll sum = 0;
    bool ok = false;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        ok = true;
        dfs(v, u);
        sum += min(dp[v], edge[i].val);
    }
    dp[u] = sum;
    if(!ok) dp[u] = INF;
}
inline void init()
{
    cnt = 0;
    for(int i=1; i<=N; i++) head[i] = -1;
}
int main()
{
    scanf("%d%d%d", &N, &M, &root);
    init();
    ll w;
    for(int i=1, u, v; i <= M; i++)
    {
        scanf("%d%d%lld", &u, &v, &w);
        _add(u, v, w);
    }
    dfs(root, 0);
    printf("%lld\n", dp[root]);
    return 0;
}