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;
}