【每日一题】Rinne Loves Edges题解

Solution

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll dp[N];
struct Edge{
  int to, nextz;
  ll w;
}edge[N << 1];
int in[N];
int head[N], tot;
void addedge(int u, int v, ll w){
  edge[tot].to = v;
  edge[tot].nextz = head[u];
  edge[tot].w = w;
  head[u] = tot++;
}
int n, m, s;
void dfs(int u, int par){
  if(in[u] == 1 && u != s){ // 叶子节点 且不是 s
    dp[u] = inf;
    return ;
  }
  for(int i = head[u]; i != -1; i = edge[i].nextz){
    int v = edge[i].to;
    if(v == par) continue;
    ll w = edge[i].w;
    dfs(v, u);
    dp[u] += min(dp[v], w);
    //cout << dp[v] << ' ' << w << "\n";
  }
}
int main(){
  memset(head, -1, sizeof(head));
  cin >> n >> m >> s;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    ll w;
    cin >> u >> v >> w;
    addedge(u, v, w);
    addedge(v, u, w);
    in[u]++, in[v]++; // 度
  }
  dp[s] = 0;
  dfs(s, -1);
  cout << dp[s] << "\n";
  return 0;
}