fr.cpp

#include <iostream>
#include <stdlib.h>
using namespace std;
 
int *connections;
int *efforts;
int nconnections[1000];
int nnodes;
int central;
 
#define pos(a,b) ((a)*1000+(b))
#define min(a,b) ((a)<(b)?(a):(b))
 
#define DEBUG
 
int calculate(int me, int sourcenode) {
    int p;
    int ret=0;
    int indiv;
    int target;
 
    // go through all pipes
    for(p=0;p<nconnections[me];p++) {
        // get ID of the target node
        target=connections[pos(me,p)];
 
        //is this the source pipe?
        if(target==sourcenode) continue;
 
        //is this a pipe with minimal effort?
        if(efforts[pos(me,p)]==1) {
            // then there's no need to calculate the rest of this sub-tree
            ret += 1;
            continue;
        }
 
        //is this a pipe with a rose-head?
        if(nconnections[target]==1) {
            ret += efforts[pos(me,p)];
            continue;
        }
 
        //... so it's a regular pipe
        indiv=calculate(target,me);
        ret+= min(efforts[pos(me,p)],indiv);
    }
    return ret;
}
 
int main() {
    int i;
    int a,b,c,w;
 
    connections=(int*)malloc(1000*1000*sizeof(int));
    efforts=(int*)malloc(1000*1000*sizeof(int));
    while(cin >> nnodes >> central) {
        // init
        central--;
        for(i=0;i<nnodes;i++) {
            nconnections[i]=0;
        }
 
        // build graph
        for(i=1;i<nnodes;i++) {
            cin >> a >> b >> w;
            a--;
            b--;
            c=nconnections[a]++;
            connections[pos(a,c)]=b;
            efforts[pos(a,c)]=w;
            c=nconnections[b]++;
            connections[pos(b,c)]=a;
            efforts[pos(b,c)]=w;
        }
 
        cout << calculate(central,-1) << endl;
    }
    free(connections);
    free(efforts);
    return 0;
}