SAC E#1

简单树形dp

#include<cstdio>
#include<algorithm>
const int maxn = 100100;
struct T{
    int to,nxt,v;
}way[maxn<<1];
int h[maxn],num;
inline void adde(int x,int y,int v){
    way[++num]={y,h[x],v},h[x]=num;
    way[++num]={x,h[y],v},h[y]=num;
}
int vis[maxn];
typedef long long ll;
ll f[maxn];
inline void dfs(int x){
    vis[x]=1;int cnt=0;
    for(int i=h[x];i;i=way[i].nxt)
        if(!vis[way[i].to])
            dfs(way[i].to),f[x]+=std::min((ll)way[i].v,f[way[i].to]),++cnt;
    if(cnt==0)f[x]=2e9;
}
int n,s;
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1,x,y,v;i<n;++i)scanf("%d%d%d",&x,&y,&v),adde(x,y,v);
    dfs(s),printf("%lld
",f[s]);
}