Rinne Love Edges 题解

刚刚做了二叉苹果树过来的，然后把这题秒了。感觉比二叉苹果树简单很多。
二叉苹果树题解：https://blog.nowcoder.net/n/c8a9812aa008472b8b31391e7995e29c

跟二叉苹果树同样的思路，把边权下放到点权，这里不再赘述，跑一遍树的构造，再进行dfs记忆化dp。
边界是叶子结点，dp[叶子]=val[叶子]
其他结点，要么把儿子割掉，要么让儿子这颗子树已经割掉了叶子。
dp[root]= min(val[son],dp[son])

本题注意事项：
1.N为1e5，所以不能用邻接矩阵，最好用链式前向星同时存边的起点终点和边权
2.题目说了long long范围内，按理说不开long long要见祖宗，不过我int也AC了
3.用重要点s作为根跑下树的构造，因为你最后要用dp[s]作为答案的

以下是代码：

//下放边权变为点权，对于每一个子树，要么加上儿子的点权，要么加上儿子为结点的整个子树的dp值

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=100100;
struct Edge
{
    int v,w,next;
}e[N<<1];
int cnt=0;
int head[N];
int val[N];
int dp[N];
bool haveson[N];
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void pushdown(int root,int pre)
{
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        haveson[root]=true;
        pushdown(to,root);
        val[to]=e[i].w;
    }
}
void dfs(int root,int pre)
{
    if(!haveson[root]) dp[root]=val[root];
    for(int i=head[root];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        dfs(to,root);
        dp[root]+=min(dp[to],val[to]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    while(m--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    pushdown(s,0);
    dfs(s,0);
    printf("%d\n",dp[s]);
}