# Poj Solution 1714

```http://poj.org/problem?id=1714

#include <stdio.h>
#include <algorithm>
using namespace std;

struct node
{
int id;
int order;
node *l,*r,*f;
int lv,rv,fv;
}tree[600];

node *leaf[600];

int n, k;
int e[600][3];
int v[600][3];
int d[600];

inline bool isleaf( node *s )
{
return s->id < k;
}

int creat( node *r, node *f , int fv )
{
int i, lo, ro;

r -> f = f;
r -> fv = fv;
if( isleaf( r ) ) return r -> order;

r -> lv = -1;

for( i=0; i<3; i++ )
{
if( e[r->id][i] != f - tree )
{
if( r -> lv == -1 )
{
r->lv = v[r->id][i];
r->l = tree+e[r->id][i];
lo = creat( r->l, r, r->lv );
}
else
{
r->rv = v[r->id][i];
r->r = tree+e[r->id][i];
ro = creat( r->r, r, r->rv );
}
}
}

if( lo > ro )
{
std::swap( r->l, r->r );
std::swap( r->lv, r->rv );
r -> order = ro;
}
else r -> order = lo;

return r -> order;
}

void init()
{
int i, j, a, b, va, h, t, g;

scanf( "%d%d", &n, &k );

for( i=0; i<n; i++ )
d[i] = 0,tree[i].id = i;

for( i=0; i< 3*n/2 ; i++ )
{
scanf( "%d%d%d", &a, &b, &va );
a--,b--;
e[a][ d[a] ] = b;
v[a][ d[a] ] = va;
d[a]++;

e[b][ d[b] ] = a;
v[b][ d[b] ] = va;
d[b]++;
}

for( i=0; i<3; i++ )
if( isleaf( tree+e[0][i] ) )
{
tree[0].l = tree+e[0][i];
tree[0].lv = v[0][i];
break;
}

h = e[0][i];

for( j=1,t=0; h!=0; j++  )
{
tree[h].order = j;
leaf[j] = tree+h;

for( i=0; i<3; i++ )
{
if( e[h][i] == t )
{
tree[h].l = tree+e[h][i];
tree[h].lv = v[h][i];
}
else if( isleaf( tree+e[h][i] ) )
{
tree[h].r = tree+e[h][i];
tree[h].rv = v[h][i];
g = e[h][i];
}
}

t=h;
h=g;
}
tree[0].r = tree+t;
tree[0].rv = tree[t].rv;

for( i=0; i<3; i++ )
{
if( e[0][i] != tree[0].l-tree && e[0][i] != tree[0].r-tree )
{
tree[0].f = e[0][i] + tree;
tree[0].fv = v[0][i];
break;
}
}

creat(     tree[0].f , tree, tree[0].fv );

}

int *output, m;

int calc_a_r( node *a, node *b, node *r );
int calc_r_b( node *a, node *b, node *r );

int calc_a_b( node *a, node *b, node *r )
{
int ans = 0;

if( a == b )
{
output[m++] = r->id;
return 0;
}

ans +=    calc_a_r( a, leaf[r->r->order-1], r->l );
output[m++] = r->id;
ans +=     calc_r_b( leaf[r->r->order], b, r->r ) + r->lv + r->rv;

return ans;
}

int calc_a_r( node *a, node *b, node *r )
{
int ans;

if( a == b )
{
output[m++] = r->id;
return 0;
}

ans =    calc_a_b( a, leaf[r->r->order-1], r->l ) +
calc_a_r( leaf[r->r->order], b, r->r ) +
r->rv + leaf[r->r->order]->lv;
output[m++] = r->id;

return ans;
}

int calc_r_b( node *a, node *b, node *r )
{

output[m++] = r->id;

if( a == b ) return 0;

return    calc_r_b( a, leaf[r->r->order-1], r->l ) +
calc_a_b( leaf[r->r->order], b, r->r ) +
r->lv + leaf[r->r->order]->lv;
}

int main()
{
int i, ans1, ans2, ans3;

init();

m = 0; output = answer[0];
ans1 = calc_a_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].rv;

m = 0; output = answer[1];
ans2 = calc_a_r( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].fv;

m = 0; output = answer[2];
ans3 = calc_r_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].rv + tree[0].fv;

if( ans1 <= ans2 && ans1 <= ans3 )