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 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;
}