题目:
https://www.luogu.com.cn/problem/P1364
题目描述
设有一棵二叉树，如图：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 1。如上图中，若医院建在 1 处，则距离和 =4+12+2×20+2×40=136；若医院建在 3 处，则距离和 =4×2+13+20+40=81。
输入格式
第一行一个整数 n，表示树的结点数。
接下来的 n 行每行描述了一个结点的状况，包含三个整数 w,u,v，其中 w 为居民人口数，u 为左链接（为 0 表示无链接），v 为右链接（为 0 表示无链接）。
输出格式
一个整数，表示最小距离和。
输入输出样例
输入
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
输出
81
说明/提示
数据规模与约定
对于 100% 的数据，保证 1≤n≤100，0≤u,v≤n，1≤w≤105。
思路：
1.我们可以使用结构体类型的数组来模拟树
2.枚举法，对每一个节点进行一次深搜，寻找出最短距离和
3.注意每行输入第2个和第3个值的时候，实际上是在输入当前节点的需要接入的节点的索引。所以我们要num[索引] = i;就相当于没有运算到索引的节点的时候，提前将索引节点的父亲节点连接好了
代码如下：
#include<iostream>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N = 1e5+5;
int n;
int sum;
int ans = INT_MAX;
struct Node{int father;int left;int right;int value;
};
bool stl[N];//记录索引每个节点是否走过
Node num[N];
int dfs(int step,int pos)//step为走了多少步，pos为当前节点的索引
{sum = sum + step * num[pos].value;int fa = num[pos].father;int l = num[pos].left;int r = num[pos].right;if(fa && stl[fa] == false){stl[fa] = true;dfs(step + 1,fa); }if(l && stl[l] == false){stl[l] = true;dfs(step + 1,l); }if(r && stl[r] == false){stl[r] = true;dfs(step + 1,r); }return sum;
}
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++){cin >> num[i].value >> num[i].left >> num[i].right;//将题目输入的索引，num[索引]我称之为节点，将这两个节点的father = i,相当于连接到当前节点i num[num[i].left].father = i;num[num[i].right].father = i;}for(int i = 1 ; i <= n ; i++){sum = 0;memset(stl,false,sizeof(stl));stl[i] = true;ans = min(ans,dfs(0,i));} cout << ans;return 0;} 