咕咕咕
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前言
> 此部分并不会影响您的阅读,可以跳过
本文默认读者已具备独立写出初阶 DP 的能力
关于创作原因
1.听说 CSP 前发学术内容可以 RP++。
2.@Lyzc0dr
>
这位的言论让我很红温。
引用文献
为什么讲换根
因为我们老师最近刚讲换根 DP,打算写一篇来巩固记忆。
往期NH精华帖
正文
1.概念
我们知道 DP 实际上就是对于一个问题的一种动态决策,而换根 DP 顾名思义,就是在树上进行的 DP,而且不会指定某一处作为根,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。
这种 DP 一般会通过 2 次 DFS 来实现,一次初始化,一次进行状态转移。
让我们用一道例题来引入。
2.用法
[POI 2008] STA-Station
形式化翻译:
给定一颗 nnn 节点的树 TTT,定义 D(u,v)D(u,v)D(u,v) 为从节点 uuu 到 vvv 的简单路径长度(包括 u,vu,vu,v),求出:
max1≤u≤n(∑1≤i≤nD(u,i))\max_{1 \le u \le n}( \sum_{1 \le i \le n} D(u,i)) 1≤u≤nmax (1≤i≤n∑ D(u,i))
解法:
显然,根据形式化翻译,我们对于每一个根节点都做一次 DFS 显然是不行的。
那么,根据 DP 的定义,我们可不可以从一个点的最优结果推出另一个点的最优结果呢?
答案是可以的。
如图为样例所代表的树(作者电脑画图技术一坨,所以用手画,望见谅):
如图,我们显然可以发现若我们从节点 444 到节点 555,对于 1,3,21,3,21,3,2 来说,其对答案的贡献就会同时加上 4→54 \to 54→5 这一段的长度 111;同理,对于 5,6,7,85,6,7,85,6,7,8 来说,其对答案的贡献就会同时减少 5→45 \to 45→4 这一段的长度 111,总共的以 555 为根节点对答案的贡献相对以 444 为根节点增加 −1-1−1
因此,我们就可以用 dpidp_idpi 表示以 ∑1≤u≤nD(i,u)\sum_{1 \le u \le n} D(i,u)∑1≤u≤n D(i,u),即以 iii 为根节点的答案。
结合上文对从节点 444 到节点 555 的分析,可以引申到如果从 u→vu \to vu→v(其中 uuu 为 vvv 的父亲)去更新 dpvdp_vdpv 的话,那么相对 dpudp_udpu 来说, 所有以 vvv 为根的子树中的节点对答案的贡献都会相对 uuu 减少 v→uv \to uv→u 这一段的长度 111。同时,所有不是以 vvv 为根的子树中的节点对答案的贡献都会相对 uuu 增加 u→vu \to vu→v 这一段的长度 111。
因此,令 sus_usu 为 uuu 的子树大小(包括 uuu),faufa_ufau 为节点 uuu 的父亲,那么就有:
dpu=dpfau−su+(n−su)dp_u=dp_{fa_u}-s_u+(n-s_u) dpu =dpfau −su +(n−su )
其中 sus_usu 可以通过一次 DFS 预处理出来,然后就可以用 DFS 自上而下求出 dpu(1≤u≤n)dp_u(1 \le u \le n)dpu (1≤u≤n),最后的答案就是:
max1≤u≤n(dpu)\max_{1 \le u \le n}(dp_u) 1≤u≤nmax (dpu )
如果不懂的话可以自行画图分析。
知道了思路,你应该就可以自行写代码了吧:)
以防你不会,给出代码:
为什么不能自底向上搜索
显然,这样的话对于 u,fav=uu,fa_v=uu,fav =u 来说,uuu 在转移过程中的 dpvdp_vdpv 中又包含其他的 dpv1dp_{v_1}dpv1 ,具有后效性,不满足 DP 性质。
现在,让我们做一些例题吧.
3.例题
[USACO10MAR] Great Cow Gathering G
和上一题是基本一样的,只不过有了点权,只需要在初始化时令 su=valus_u=val_usu =valu 就可以了,代码基本一样.
4.进阶
后记