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 answer[3][500];
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 )
output = answer[0];
else if( ans2 <= ans1 && ans2 <= ans3 )
output = answer[1];
printf( "%d", 1 );
for( i=0; i<n-1; i++ )
printf( " %d", output[i]+1 );
printf( "n" );
return 0;
}