学步园

题目描述

设有一棵二叉树，其中圈中的数字表示结点居民的人口，圈边上的数字表示结点的编号。现在要求在某个结点上建立一个医院，使所有居民所走的路径之和为最小，同时约定，相邻接点之间的距离为1，就本图而言，若医院建在1处，则距离和＝4＋12＋2＊20＋2＊40＝136，若医院建在3处，则距离和＝4＊2＋13＋20＋40＝81，…
输入格式

其中第一行一个整数n，表示树的结点数（n<=100）。接下来的N行每行描述了一个结点的状况，包括三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。
输出格式

只有一个整数，表示最小距离和。
样例输入
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
样例输出
81

此題考察帶權中位數在二叉樹中的應用。
線性帶權中位數：

有一系列數據（排序後）a1, a2, a3, ..., an，它們每都有一個權值w1, w2, w3, ..., wn，則這一系列數據中位數為：到所有數的帶權距離和最小的數值。（當然和數學中的帶權中位數不一樣，這裡的中位數必須等於某一個數ai。）

並且容易知道，ai到比其小的所有帶權距離和與到比其大的所有帶權距離和的差值最小，也即ai到a1, a2, ..., a(i-1)的帶權距離和剛好大於ai到所有點帶權距離和的一半。

在樹上的帶權中位數即為到所有點帶權距離和剛好大於到所有點帶權距離和的一半，而把線性帶權中位數中的左右枚舉轉變為這裡的枚舉各個子樹，代價分析即分析從根節點到每一個子樹的代價變化。
ACCode：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>

using std::bitset;

const char fi[] = "rqnoj319.in";
const char fo[] = "rqnoj319.out";
const int maxN = 110;
const int MAX = 0x3fffff00;
const int MIN = -MAX;

bitset <maxN> tmp;
int g[maxN];
int d[maxN];
int lc[maxN], rc[maxN];
int n, root, L, R, ans, sum;

  void init_file()
  {
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
  }
    
  void readdata()
  {
    scanf("%d", &n);
    for (int i = 1; i < n + 1; ++i)
    {
      scanf("%d%d%d", g + i, lc + i, rc + i);
      sum += g[i];
      if (lc[i]) tmp.set(lc[i]);
      if (rc[i]) tmp.set(rc[i]);
    }
    for (int i = 1; i < n + 1; ++i)
      if (!tmp.test(i)) {root = i; break; }
  }
  
  void Dfs1(int i, int deep)
  {
    ans += deep * g[i];
    if (lc[i]) Dfs1(lc[i], deep + 1);
    if (rc[i]) Dfs1(rc[i], deep + 1);
    g[i] += g[lc[i]] + g[rc[i]];
  }
  
  void Dfs2(int i)
  {
    if ((g[lc[i]] << 1) > sum)
    {
      ans -= (g[lc[i]] << 1) - sum;
      if (lc[i]) Dfs2(lc[i]);
    }
    if ((g[rc[i]] << 1) > sum)
    {
      ans -= (g[rc[i]] << 1) - sum;
      if (rc[i]) Dfs2(rc[i]);
    }
  }
  
  void work()
  {
    Dfs1(root, 0);
    Dfs2(root);
    printf("%d", ans);
  }
  
int main()
{
  init_file();
  readdata();
  work();
  exit(0);
}