fr.cpp

#include <cstdio>
#include <vector>
using namespace std;
 
struct Node
{
	int num;
	int effort;
	int min;
	vector<int> children;
	int parent;
 
	Node( int n = 0, int p = 0 )
	{
		num = n;
		parent = p;
	}
 
	void add( int n )
	{
		children.push_back(n);
	}
 
	int ccount()
	{
		return children.size();
	}
};
 
int bublej( Node * node, Node ** graph, int parent )
{
	if( node->ccount() == 1 )
	{
		//printf( "jsem %d a vracim %d\n", node->num, node->effort );
		return node->effort;
	}
 
	//printf( "jsem %d a prisel jsem z %d\n", node->num, parent );
 
	int sum = 0;
	for( int i = 0; i < node->ccount(); i++ )
	{
		if( node->children[i] == parent )
			continue;
 
		int b = bublej( graph[ node->children[i]-1 ], graph, node->num );
 
		//printf( "sum (%d) += %d\n", sum, b );
		sum += b;
	}
 
	//printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum );
	if( sum < node->effort )
		node->effort = sum;
 
	return node->effort;
}
 
int main()
{
	int nodec, center;
	while( scanf("%d %d\n", &nodec, &center) == 2 )
	{
		Node ** nodeArr = new Node*[nodec];
		for( int i = 0; i < nodec; i++ )
			nodeArr[i] = new Node(i+1);
 
		nodeArr[center-1]->effort = 2000;
 
		for( int i = 0; i < nodec-1; i++ )
		{
			int n,c,e;
			scanf( "%d %d %d\n", &n,&c,&e );
 
			if( c != center )
				nodeArr[c-1]->effort = e;
			else
				nodeArr[n-1]->effort = e;
 
			nodeArr[n-1]->add(c);
			nodeArr[c-1]->add(n);
		}
 
		/*
		for( int i = 0; i < nodec; i++ )
		{
			printf( "Node%d (%d) : ", nodeArr[i]->num, nodeArr[i]->effort );
			for( int j = 0; j < nodeArr[i]->ccount(); j++ )
				printf( " %d", nodeArr[i]->children[j] );
			printf( "\n" );
		}
		*/
 
		int result = bublej( nodeArr[center-1], nodeArr, 0 );
		printf( "%d\n", result );
	}
 
	return 0;
}