fr.cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef unsigned long int ulint;
struct edge
{
edge() : dest(), w(0) {}
edge(int dest, int w) : dest(dest), w(w) {}
int dest;
int w;
};
edge graph[1020][1020];
int N;
int M;
int graph_out[1020];
int graph_out2[1020];
int parent[1020];
queue<int> Q;
int D[1020];
int R;
bool visited[1020];
void clear()
{
M = 0;
N = 0;
fill(graph_out, graph_out + 1020, 0);
fill(graph_out2, graph_out2 + 1020, 0);
fill(D, D + 1020, 0);
fill(visited, visited + 1020, false);
while (!Q.empty())
{
Q.pop();
}
}
void solve_parents(int u)
{
visited[u] = true;
for (int i = 0; i < N; ++i)
{
if (!visited[graph[u][i].dest])
{
parent[graph[u][i].dest] = u;
solve_parents(graph[u][i].dest);
}
}
}
void solve()
{
parent[R] = 1010;
solve_parents(R);
// ADD leafs to Q
for (int i = 0; i < N; ++i)
{
if (graph_out2[i] == 1)
{
Q.push(i);
}
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
ulint sum = 0;
for (uint j = 0; j < graph_out[u]; ++j)
{
if (graph[u][j].dest == parent[u]) continue;
if (D[graph[u][j].dest])
{
sum += min(D[graph[u][j].dest], graph[u][j].w);
}
else
{
sum += graph[u][j].w;
}
}
D[u] = sum;
graph_out2[parent[u]]--;
if (graph_out2[parent[u]] == 1)
{
//cerr << "new leaf\n";
Q.push(parent[u]);
}
}
printf("%d\n", D[R]);
}
int main()
{
clear();
while (scanf("%d %d", &N, &R) != EOF)
{
for (int i = 0; i < N - 1; ++i)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
graph[u][graph_out[u]++] = edge(v, w);
graph[v][graph_out[v]++] = edge(u, w);
graph_out2[u]++;
graph_out2[v]++;
}
solve();
clear();
}
}