fr.cpp

#include<iostream>
 
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
 
#include<vector>
#include<queue>
 
using namespace std;
 
#define FOR(i,a,b) for(int i=a; i<=b; i++)
 
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
 
#define SIZE(s) ((int)(s).size())
 
#define ll long long
#define INF 987654321
#define MAX 1047
#define fi first
#define se second
 
vector< PII > G[MAX];
int N, V;
 
int visits[MAX];
int values[MAX];
 
PII find(int v)
{
	FOR(i,0,SIZE(G[v])-1)
		if ( !visits[ G[v][i].fi ])
			return G[v][i];
	return MP(0,0);
}
 
vector<int> D[MAX];
int max_depth;
 
void dfs(int v, int depth)
{
	max_depth = max(depth, max_depth);
	D[depth].PB(v);
	visits[v] = true;
	FOR(i,0,SIZE(G[v])-1)
		if (!visits[ G[v][i].fi ])
			dfs( G[v][i].fi , depth+1);
}
 
 
int main()
{
	int a, b, c;
	while(scanf("%d %d", &N, &V) == 2)
	{
		V--;
		FOR(i,0,N-1) G[i].clear();
		FOR(k,1,N-1)
		{
			scanf("%d %d %d",&a, &b, &c);
			a--; b--;
			G[a].PB( MP(b, c) );
			G[b].PB( MP(a, c) );
		}
 
 
		max_depth = 0;
		FOR(i,0,N) D[i].clear();
		FOR(i,0,N-1) visits[i]= false;
		dfs(V,0);
/*
		FOR(d,0,max_depth)
		{
			cout << "d: " << d << " - ";
			FOR(i,0,SIZE(D[d])-1)
				cout << D[d][i]+1 << " ";
			cout << endl;
		}
*/
		FOR(i,0,N-1)
			values[i] = 0;
 
		FOR(i,0,N-1)
			if (SIZE(G[i]) == 1 && i != V)
				values[i] = INF;
 
		FOR(i,0,N-1) visits[i] = false;
		for(int d = max_depth; d>=0; d--)
			FOR(i,0,SIZE(D[d])-1)
			{
				int v = D[d][i];	
				visits[v] = true;
				PII parent = find(v);
				values[parent.fi ] += min( values[v], parent.se );
 
 
		//		cout << "som na " << v+1 << endl;
		//		cout << "davam do " << parent.fi+1 << " - " <<  min( values[v], parent.se ) << endl; 
			}
 
	//	FOR(i,0,N-1) cout << i+1 << ". " << values[i] << endl;
 
		printf("%d\n", values[V] );
	}
	return 0;
}