Rinne Loves Edges

Problem:

给你一个由N个点和N-1条无向边组成的连通图(树),每条边有对应的权值,问通过删除一些边后使任何度数为1(叶子)都不能到达S点,
删除边的价值和最小是多少?

Solution:

Problem的括号中就是重要的信息,所以我们只需要以S为根,然后从叶子节点往上计算使当前节点不能到达叶子节点所需要删除边的最小权值即可
dp[nowp] += min(dp[v],w);nowp为当前节点,v为当前节点的儿子节点,w为两个点边上面的权值。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
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;
}
typedef long long ll;
const int maxn = 1e5 + 10;
int n,m,s;
struct Node{
    int id,w;
    Node(){}
    Node(int _id,int _w):id(_id),w(_w){}
};
vector<Node> G[maxn];
ll dp[maxn];
void dfs(int nowp,int fa){
    int siz = G[nowp].size();
    _for(i,0,siz){
        int v = G[nowp][i].id;
        if(v == fa){
            if(siz == 1){
                dp[nowp] = INF;
            }    
            continue;
        }
        dfs(v,nowp);
        dp[nowp] += min(dp[v],G[nowp][i].w * 1ll);
    }
}
int main(){
    IOS;
    cin>>n>>m>>s;
    int u,v,w;
    rep(i,1,m){
        cin>>u>>v>>w;
        G[u].push_back(Node(v,w));
        G[v].push_back(Node(u,w));
    }
    dfs(s,0);
    cout<<dp[s]<<endl;
    return 0;
}
/**
Problem:
    给你一个由N个点和N-1条无向边组成的连通图(树),每条边有对应的权值,问通过删除一些边后使任何度数为1(叶子)都不能到达S点,
    删除边的价值和最小是多少? 
Solution:
    Problem的括号中就是重要的信息,所以我们只需要以S为根,然后从叶子节点往上计算使当前节点不能到达叶子节点所需要删除边的最小权值即可
    dp[nowp] += min(dp[v],w);nowp为当前节点,v为当前节点的儿子节点,w为两个点边上面的权值。 
*/