问题
一个二叉树共有n个节点，范围为[1,n]，每个节点拥有一个权值，所有节点的权值之和不超过m。从任意节点i都可以到达另一节点j，且路线是唯一的，每一条的距离为1（节点与自己的距离为0，与其父节点、左右孩子节点的距离为1）。设节点i权值为vi，所有到节点i的距离小于等于radius的节点权值之和为∑p=1nivp 。称该权值之和为节点i在半径radius上的半径和。下图演示了节点4覆盖到的半径为2的区域：
求二叉树的最大半径和。
解法
根据上图我们可以看出，找出节点i半径radius内的所有节点并求和，即可得到该节点的半径和。二叉树中沿着父节点向上移动，和沿着左右孩子向下移动的操作不一样，因此将其区分。设f(i,j)表示节点i在半径为j的范围内，只沿着父节点向上移动的半径和，则有状态转移方程：
f(i,j)={0f(fatheri,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,fatheri∈[1,n],0≤j−1<j≤m (1) 初始化，向上半径为0时节点i的半径和为0，即g(i,0)=0；
(2) 节点i在半径j上向上的半径和，显然等于它的父结点fatheri在半径为j−1上的半径和与它自己的权值之和，即f(i,j)=f(fatheri,j−1)+vi；
下图演示节点7向上半径为3所覆盖到的节点：
设g(i,j)表示节点i在半径j的范围内，只沿着左右孩子节点向下移动的半径和，则有状态转移方程：
g(i,j)={0g(lefti,j−1)+g(righti,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,lefti,righti∈[1,n],0≤j−1<j≤m (1) 初始化，向下半径为0时节点i的半径和为0，即g(i,0)=0；
(2) 节点i在半径j上向下的半径和，显然等于它的左右孩子节点lefti,righti在半径为j−1上的半径和与它自己的权值之和，即g(i,j)=g(lefti,j−1)+g(righti,j−1)+vi；
下图演示节点1向下半径为3所覆盖到的节点：
还漏掉了节点i的叔叔节点unclei，下图演示节点4在半径2上覆盖到的所有节点，其中没有被f(4,2)和g(4,2)覆盖到的节点用绿色标记：
设h(i,j)为节点i在半径j上的半径和（本问题所求），则有状态转移方程：
h(i,j)={0f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,fatheri,unclei,lefti,righti∈[1,n],0≤j−2<j−1<j≤m (1) 初始化，半径为0时节点i的半径和为0，即h(i,0)=0；
(2) 节点i在半径j上的半径和，显然等于它的父节点、左右孩子节点在半径为j−1上的半径和，以及叔叔节点在半径为j−2上的半径和，与它自己的权值之和，即h(i,j)=f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vi；
遍历二叉树上所有节点，找出最大的半径和即可。该算法的时间复杂度为O(n×m)。
Cow Travelling
源码
测试
