gitbook-way-to-algorithm
  • Introduction
  • Preface 前言
  • Content 目录
  • MathSymbolTable 数学符号表
  • Chapter-1 BasicKnowledge 第1章 基础知识
    • TimeComplexity 时间复杂度
    • Recursion 递归式
  • Chapter-2 Sort 第2章 排序
    • InsertSort 插入排序
    • BubbleSort 冒泡排序
    • QuickSort 快速排序
    • MergeSort 归并排序
  • Chapter-3 Search 第3章 搜索
    • BinarySearch 二分查找法(折半查找法)
    • AdditionMultiplicationPrinciple 加法乘法原理
    • BruteForce 暴力枚举
    • Recursion 递归
    • BreadthFirstSearch 广度优先搜索
    • BidirectionalBreadthSearch 双向广度搜索
    • AStarSearch A*搜索
    • DancingLink 舞蹈链
  • Chapter-4 DataStructure 第4章 数据结构
    • DisjointSet 并查集
    • PrefixTree(TrieTree) 前缀树
    • LeftistTree(LeftistHeap) 左偏树(左偏堆)
    • SegmentTree 线段树
    • FenwickTree(BinaryIndexedTree) 树状数组
    • BinarySearchTree 二叉查找树
    • AVLTree AVL平衡树
    • RedBlackTree 红黑树
    • SkipList 跳跃表
    • BPlusTree B+树
    • BMinusTree B-树
  • Chapter-5 DynamicProgramming 第5章 动态规划
    • Section-1 LinearDP 第1节 线性动规
      • LongestCommonSubsequence 最长公共子序列
      • LongestIncreasingSubsequence 最长递增子序列
      • BidirectionalSubsequence 双向子序列
      • MaximumContinuousSubsequenceSum 最大连续子序列和
      • LongestPalindromicSubsequence 最长回文子序列
    • Section-2 BagDP 第2节 背包问题
      • 01-Bag 01背包
      • CompleteBag 完全背包
      • TwoDimensionBag 二维背包
    • Section-3 RegionalDP 第3节 区域动规
      • MinimumMergeCost - 最小合并代价
      • UniquePath 唯一路径
      • TrianglePath 三角形路径
    • Section-4 TreeDP 第4节 树形动规
      • MaximumBinaryTree 最大二叉树
      • MaxMultipleTree 最大多叉树
      • MaximumBinaryTreeRadiusSum 最大二叉树和
  • Chapter-6 GraphTheory 第6章 图论
    • Section-1 Traverse 第1节 遍历
      • DepthFirstSearch 深度优先搜索
      • BreadthFirstSearch 广度优先搜索
      • TopologicalSort 拓扑排序
      • EulerCycle 欧拉回路
    • Section-2 MinSpanningTree 第2节 最小生成树
      • Kruskal Kruskal算法
      • Prim Prim算法
    • Section-3 ShortestPath 第3节 最短路径
      • BellmanFord BellmanFord算法
      • Dijkstra Dijkstra算法
      • FloydWarshall FloydWarshall算法
      • DifferentConstraints 差分约束
    • Section-4 StronglyConnectedComponents 第4节 强连通分支
      • Kosaraju Kosaraju算法
      • Tarjan Tarjan算法
      • 2-SAT 2-SAT问题
    • Section-5 NetworkFlow 第5节 网络流
      • EdmondsKarp EdmondsKarp算法(最短路径增广算法)
      • PushRelabel 压入与重标记算法
      • Dinic - Dinic算法
      • MinimumCostFlow - 最小费用流
      • MultipleSourceMultipleSinkMaxflow - 多源点多汇点最大流
    • Section-6 BinaryMatch 第6节 二分匹配
      • Hungarian 匈牙利算法
      • HopcroftKarp Hopcroft-Karp算法
      • MatchToMaxflow 二分匹配转化为最大流
      • KuhnMunkres Kuhn-Munkres算法
      • Introduction-Domination,Independent,Covering,Clique 介绍支配集、独立集、覆盖集和团
      • WeightedCoveringAndIndependentSet 最小点权覆盖和最大点权独立集
      • MinimumDisjointPathCovering 最小不相交路径覆盖
      • MinimumJointPathCovering 最小可相交路径覆盖
      • Coloring 染色问题
  • Chapter-7 CombinatorialMathematics 第7章 组合数学
    • FullPermutation 全排列
    • Combination 组合
    • Permutation 排列
    • PermutationGroup 置换群
  • Chapter-8 NumberTheory 第8章 数论
    • PrimeSieve 素数筛法
    • GreatestCommonDivisor 最大公约数
    • Euclid 欧几里得算法
    • ExtendedEuclid 扩展欧几里得算法
    • ChineseRemainerTheorem 中国剩余定理
    • ModularExponentiation 模幂运算
  • Chapter-9 LinearAlgebra 第9章 线性代数
    • Section-1 Matrix 第1节 矩阵
      • Strassen Strassen算法
      • GaussElimination 高斯消元法
      • LUP LUP分解
      • InverseMatrix 矩阵求逆
    • Section-2 LinearProgramming 第2节 线性规划
      • Simplex 单纯形算法
      • Dinkelback Dinkelback算法
  • Chapter-10 AnalyticGeometry 第10章 解析几何
    • Section-1 Polygon 第1节 多边形
      • Cross 向量叉积
      • SegmentIntersection 线段相交
      • Sweeping 扫除算法
      • ConvexPolygonArea 凸多边形面积
      • ConvexPolygonGravityCenter 凸多边形重心
      • NearestNeighbor 最近点对
    • Section-2 ConvexHull 第2节 凸包
      • GrahamScan Graham扫描算法
      • QuickHull 快速凸包算法
      • RotatingCalipers 旋转卡壳
  • Chapter-11 PatternMatch 第11章 文本匹配
    • SimpleMatch 简单匹配
    • AhoCorasickAutomata AC自动机
    • KnuthMorrisPratt KMP匹配算法
    • RabinKarp RabinKarp算法
    • BoyerMoore BoyerMoore算法
  • Chapter-12 GameTheory 第12章 博弈论
    • BashGame 巴什博弈
    • WythoffGame 威佐夫博弈
    • NimGame 尼姆博弈
Powered by GitBook
On this page
  • 问题
  • 解法
  • Cow Travelling
  • 源码
  • 测试
  1. Chapter-5 DynamicProgramming 第5章 动态规划
  2. Section-4 TreeDP 第4节 树形动规

MaximumBinaryTreeRadiusSum 最大二叉树和

PreviousMaxMultipleTree 最大多叉树NextChapter-6 GraphTheory 第6章 图论

Last updated 6 years ago

问题

一个二叉树共有nnn个节点,范围为[1,n][1,n][1,n],每个节点拥有一个权值,所有节点的权值之和不超过mmm。从任意节点iii都可以到达另一节点jjj,且路线是唯一的,每一条的距离为1(节点与自己的距离为0,与其父节点、左右孩子节点的距离为1)。设节点iii权值为viv_{i}vi​,所有到节点iii的距离小于等于radiusradiusradius的节点权值之和为∑p=1nivp\sum_{p=1}^{n_{i}} v_{p}∑p=1ni​​vp​ 。称该权值之和为节点iii在半径radiusradiusradius上的半径和。下图演示了节点444覆盖到的半径为222的区域:

求二叉树的最大半径和。

解法

根据上图我们可以看出,找出节点iii半径radiusradiusradius内的所有节点并求和,即可得到该节点的半径和。二叉树中沿着父节点向上移动,和沿着左右孩子向下移动的操作不一样,因此将其区分。设f(i,j)f(i,j)f(i,j)表示节点iii在半径为jjj的范围内,只沿着父节点向上移动的半径和,则有状态转移方程:

f(i,j)={0(initialize)i∈[1,n],j=0f(fatheri,j−1)+vi(loop)i,fatheri∈[1,n],0≤j−1<j≤mf(i,j) = \begin{cases} 0 & (initialize) & i \in [1,n], j = 0 \\ f(father_{i}, j-1) + v_{i} & (loop) & i, father_{i} \in [1,n], 0 \leq j-1 \lt j \leq m \end{cases}f(i,j)={0f(fatheri​,j−1)+vi​​(initialize)(loop)​i∈[1,n],j=0i,fatheri​∈[1,n],0≤j−1<j≤m​

(1)(1)(1) 初始化,向上半径为000时节点iii的半径和为000,即g(i,0)=0g(i,0) = 0g(i,0)=0;

(2)(2)(2) 节点iii在半径jjj上向上的半径和,显然等于它的父结点fatherifather_{i}fatheri​在半径为j−1j-1j−1上的半径和与它自己的权值之和,即f(i,j)=f(fatheri,j−1)+vif(i,j) = f(father_{i}, j-1) + v_{i}f(i,j)=f(fatheri​,j−1)+vi​;

下图演示节点777向上半径为333所覆盖到的节点:

设g(i,j)g(i,j)g(i,j)表示节点iii在半径jjj的范围内,只沿着左右孩子节点向下移动的半径和,则有状态转移方程:

g(i,j)={0(initialize)i∈[1,n],j=0g(lefti,j−1)+g(righti,j−1)+vi(loop)i,lefti,righti∈[1,n],0≤j−1<j≤mg(i,j) = \begin{cases} 0 & (initialize) & i \in [1,n], j = 0 \\ g(left_{i}, j-1) + g(right_{i}, j-1) + v_{i} & (loop) & i, left_{i}, right_{i} \in [1,n], 0 \leq j-1 \lt j \leq m \end{cases}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)(1)(1) 初始化,向下半径为000时节点iii的半径和为000,即g(i,0)=0g(i,0) = 0g(i,0)=0;

(2)(2)(2) 节点iii在半径jjj上向下的半径和,显然等于它的左右孩子节点lefti,rightileft_{i}, right_{i}lefti​,righti​在半径为j−1j-1j−1上的半径和与它自己的权值之和,即g(i,j)=g(lefti,j−1)+g(righti,j−1)+vig(i,j) = g(left_{i}, j-1) + g(right_{i}, j-1) + v_{i}g(i,j)=g(lefti​,j−1)+g(righti​,j−1)+vi​;

下图演示节点111向下半径为333所覆盖到的节点:

还漏掉了节点iii的叔叔节点uncleiuncle_{i}unclei​,下图演示节点444在半径222上覆盖到的所有节点,其中没有被f(4,2)f(4,2)f(4,2)和g(4,2)g(4,2)g(4,2)覆盖到的节点用绿色标记:

设h(i,j)h(i,j)h(i,j)为节点iii在半径jjj上的半径和(本问题所求),则有状态转移方程:

h(i,j)={0(initialize)i∈[1,n],j=0f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vi(loop)i,fatheri,unclei,lefti,righti∈[1,n],0≤j−2<j−1<j≤mh(i,j) = \begin{cases} 0 & (initialize) & i \in [1,n], j = 0 \\ f(father_{i}, j-1) + g(uncle_{i}, j-2) + g(left_{i},j-1) + g(right_{i}, j-1) + v_{i} & (loop) & i, father_{i}, uncle_{i}, left_{i}, right_{i} \in [1,n], 0 \leq j-2 \lt j-1 \lt j \leq m \end{cases}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)(1)(1) 初始化,半径为000时节点iii的半径和为000,即h(i,0)=0h(i,0) = 0h(i,0)=0;

(2)(2)(2) 节点iii在半径jjj上的半径和,显然等于它的父节点、左右孩子节点在半径为j−1j-1j−1上的半径和,以及叔叔节点在半径为j−2j-2j−2上的半径和,与它自己的权值之和,即h(i,j)=f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vih(i,j) = f(father_{i}, j-1) + g(uncle_{i}, j-2) + g(left_{i}, j-1) + g(right_{i}, j-1) + v_{i}h(i,j)=f(fatheri​,j−1)+g(unclei​,j−2)+g(lefti​,j−1)+g(righti​,j−1)+vi​;

遍历二叉树上所有节点,找出最大的半径和即可。该算法的时间复杂度为O(n×m)O(n \times m)O(n×m)。

Cow Travelling

源码

测试

http://train.usaco.org/TESTDATA/MAR08.ctravel.htm
MaximumBinaryTreeRadiusSum.h
MaximumBinaryTreeRadiusSum.cpp
MaximumBinaryTreeRadiusSumTest.cpp
MaxBinaryTreeRadiusSum1.png
MaxBinaryTreeRadiusSum2.png
MaxBinaryTreeRadiusSum3.png
MaxBinaryTreeRadiusSum4.png