three.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define DEBUG(x) cerr << ">> " << #x << ": " << x << endl;
#define REP(i,a) for (int i =0; i < (a);++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
 
struct Edge
{
  int target;
  int power;
  Edge(int to, int por)
  {
      target = to;
      power = por;
  }
};
 
struct Node
{
  vector<Edge> edges;
};
 
Node* nodes;
 
int root, nodeCount;
 
int getpower(int node, int parent, int selfpower)
{
  int sumOfSons = 0;
  if (nodes[node].edges.size() == 1 && node != root-1)
  {
    return selfpower;
  }
  for (vector<Edge>::iterator it = nodes[node].edges.begin(); it != nodes[node].edges.end(); ++it)
  {
     if (it->target == parent) continue;     
     int fromSon = getpower(it->target, node, it->power);
     sumOfSons += fromSon;
  }
  if (node == root-1) { return sumOfSons; }
  else  
  { if (sumOfSons < selfpower) { return sumOfSons; } else { return selfpower; } }
}
 
 
int main() {
  while (scanf("%d%d", &nodeCount, &root) != EOF) 
  {
    nodes = new Node[nodeCount];
    for (int i = 0; i < nodeCount-1;i++)
    {
        int from, to, epower;
        scanf("%d%d%d",&from, &to, &epower);	
	nodes[from-1].edges.push_back(Edge(to-1, epower));
	nodes[to-1].edges.push_back(Edge(from-1, epower));
    }
    printf("%d\n", getpower(root-1, -1, -1));
 
    delete[] nodes;
  }
  return 0;
}