若干树形dpの总结

洛谷P3574（POI 2014）

题目描述

在一个叫做比特村的小村庄中，有 \(n-1\) 条路连接着这个村庄中的全部 \(n\) 个房子。
每两个房子之间都有一条唯一的通路。这些房子的编号为 \(1\) 至 \(n\)。
\(1\) 号房子属于村庄的管理员比特安萨尔。
为了提升村庄的科技使用水平，\(n\) 台电脑被快递到了比特安萨尔的房子。每个房子都应该有一台电脑，且分发电脑的任务就落在了比特安萨尔的肩上。
比特村的居民一致同意去玩农场物语这个游戏的最新快照版，而且好消息是他们很快就要得到他们最新的高配置电脑了。
比特安萨尔将所有电脑都装在了他的卡车上，而且他准备好完成这个艰巨的任务了。
他的汽油恰好够走每条路两遍。
在每个房子边，比特安萨尔把电脑贴心的配送给居民，且立即前往下一个房子。（配送过程不花费任何时间）
只要每间房子的居民拿到了他们的新电脑，它们就会立即开始安装农场物语。安装农场物语所用的时间根据居民的科技素养而定。幸运的是，每间房子中居民的科技素养都是已知的。
在比特安萨尔配送完所有电脑后，他会回到他自己的 \(1\) 号房子去安装他自己的农场物语。
用卡车开过每条路的时间恰好是 \(1\) 分钟，而居民开电脑箱的时间可以忽略不计。（因为他们太想玩农场物语了）
请你帮助比特安萨尔算出从开始配送到所有居民都玩上了农场物语的最少时间。
输入格式

第一行包含一个整数 \(n(2 \leq n \leq 5\times 10^5)\)，代表比特村中有多少房子。
第二行包含 \(n\) 个整数 \(c_1, c_2, ⋯, c_n(1 \leq c_i \leq 10^9)\)，每个数都被单个空格隔开。\(c_i\) 是第 \(i\) 号房间中居民安装农场物语所用的时间。
接下来的 \(n-1\) 行代表了每一条路的两个顶点。两个顶点 \(a\) 和 \(b\) 满足 \(1 \leq a < b \leq n\)，两个数之间有一个空格。
输出格式

一行，包含一个整数，代表题目中所说的最小时间。
题解


一道很显然的树形DP。
设状态\(f_i\)代表走完以i为根子树中的最大时间。
便可以很显然的得出转移方程：\(f_i = max( f_j + t +1)\)，其中\(j\)为\(i\)的儿子，\(t\)为开始往\(j\)走时的时间。
接下来开始推转移顺序。
设\(size_u\)为走完以u为根的子树所需的时间。
令树上任意一点p的其中两个儿子为\(x\)和\(y\)
若令x先走，则\(f_p\)=\(max(f_p,t+max(f_x,f_y+size_x+2)+1)\)
反之，则\(f_p\)=\(max(f_p,t+max(f_y,f_x+size_y+2)+1)\)
则可得当让x先转移更优时，当且仅当\(size_x\)-\(f_x\)