树的遍历

dfs遍历所有结点

#include<iostream>
#include<cstring>
using namespace std;
const int N=110,M=2*N;
const int INF=0x3f3f3f3f;
int h[N],w[N],e[M],ne[M],idx=0;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}

int n;

int dfs(int u,int root,int dist)
{
    int res=w[u]*dist;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=root) res+=dfs(j,u,dist+1);
    }
    return res;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b,c; cin>>c>>a>>b;
        if(a) add(i,a);
        if(b) add(i,b);
        w[i]=c;
    }

    int res=INF;
    for(int i=1;i<=n;i++)
        res=min(res,dfs(i,-1,0));

    cout<<res;
    return 0;
}