按某一个炒鸡dalao名曰 taotao 的话说:
顺便提一下他的〔题解〕(因为按照这个思路写的,所以代码看起来也差不多)
因为比较复(胡)杂(炸),可能需要理解久一点
『题目』
参见 〔洛谷 P5024〕
『解析』
一、初步思考
如果不考虑多次询问的话,显然可以进行一次简单的树形DP,特殊判断一下当前的点(也就是城市)能不能选(放军队)就行了~ 但是显然会$TLE$。
由于$m$也就是询问次数非常大,而dp状态非常之多,不可能 $O(1)$ 的时间处理每次询问。那么剩下两种时间复杂度的可能性要么是 $O(log_2n)$ 要么是 $O(\sqrt{n})$。根据我浅薄的对算法的理解……好像没有什么用来优化dp的有关树的算法是 $O(\sqrt n)$ 的,倒是有一个树上倍增($LCA$)是 $O(log_2n)$ 的。
(至于一般的树形dp相信大家都会)
对这道题本身进行分析——假设现在被限制的点是 $u$,$v$ ,根节点是 $1$,那么:
① $lca$ 到 点$1$ 的路径上的 $dp$ 值被 $u$,$v$ 共同影响;
② $u$ 到 $lca$ 的路径上的 $dp$ 值被 $u$ 影响;
③ $v$ 到 $lca$ 的路径上的 $dp$ 值被 $v$ 影响;
恰好我们知道有一种倍增优化dp的算法,所以正解顺理成章就是树上倍增优化树形dp~(出题人的思维还是非常厉害的)
对于倍增求lca的运用不止可以求出lca,还经常用来统计两点经过lca的简单路径上的一些特殊值,其转移方法大多数是:
如果要求 u 到 u的第$2^i$个祖先 的路径上的值,就综合 u 到 u的第$2^{i-1}$个祖先 的路径上的值,和 u的第$2^{i-1}$个祖先 到 u的第$2^i$个祖先 的路径上的值;
二、倍增推导dp数组
那么对树形dp的优化也是这样的~因为一般的dp状态定义是 “dp[u][0/1] 表示u选/不选时以u为根的子树的最小花费”,那么我们定义 $fdp[u][k][0/1][0/1]$ 表示 “u选/不选(第三维)”并且 u的第$2^i$个祖先 选/不选(第四维)时,以 u的第$2^i$个祖先 为根的子树的最小花费。另外几个定义如下:
- $fa[u][i]$ 表示“点u的第$2^i$个祖先”,如果没有则值为0;
- $dep[u]$ 表示“点u的深度”;
一次DFS就可以求出 dp,dep 的值(DFS1)。
因为我们考虑了2个点的取舍,必然就会有一些之前的(没有任何限制时的最优值)是不合法的,所以我们需要对 fdp 进行一些修改。这就进入了第2次DFS:
根据 taotao 的说法,大概就是“合法的值=可能不合法的值-原有贡献+合法的贡献”
倍增求lca的基本操作——先把 u 到 u的父亲 的值处理出来,然后依次处理出 fa和fdp 。也就是说我们先要处理 $fdp[u][0][0/1][0/1]$ ,以下简称pre为u的父亲:
- fdp[u][0][0/1][0/1]=INF :因为 u 和 pre 至少有一个要选;
- fdp[u][0][1][0]=dp[pre][0] :因为如果pre不选那么u一定选;
- fdp[u][0][0][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][0]:因为选pre时,u的贡献为min(dp[u][0],dp[u][1]),但是我们必须限制u不选,所以减去它原有贡献再加上dp[u][0]也就是合法贡献;
- fdp[u][0][1][1]=dp[pre][1]-min(dp[u][0],dp[u][1])+dp[u][1]:其他的都和上面的那种情况是相同的,只不过这是限制了u必须选也就是必须产生dp[u][1]的贡献。
重要的不是递推式,是思路“合法的值=可能不合法的值-原有贡献+合法的贡献”——
假设我们现在要推导从u到u的第2^k个祖先的状态,也就是fdp[u][k][a][b](a决定u选/不选,b决定u的第2^k个祖先选/不选)
那么,我们可以根据已经得到的
①u到u的第2^{k-1}个祖先(定义为anc)的状态也就是fdp[u][k-1][a][0/1]
②anc到anc的第2^{k-1}个祖先的状态也就是fdp[anc][k-1][0/1][b]
可见anc有两种状态——选/不选,那么我们定义这个状态为c
① 那么上面说的“可能不合法的值”是指fdp[anc][k-1][c][b],因为我们并不知道这个值所代表的状态是否满足u的状态;
② “原有贡献”也就是dp[anc][c],在这种状态下,u的状态是不受限制的;
③ “合法的贡献”说的是fdp[u][k-1][a][c],这样的话也就限制了u的状态
综上所述,我们可以得到转移式:
(感觉开始difficult了)
这样的话我们就可以转移了~这就是第二次DFS(DFS2)。
三、lca求解答案
接下来就是求LCA,顺便求解答案的过程——类比之前的转移,这里的转移要点也是“合法的值=可能不合法的值-原有贡献+合法的贡献”;只是说这里的转移可以大致分为3步(下面都假设u的深度大于v):
- 将u移动到与v深度相同的位置,移动的路径就是u的状态会影响的路径;
- 将u,v同时移动到它们的lca,u,v各自移动的路径分别受u,v的状态的影响;
- 将lca移动到根节点,lca移动的路径由u,v的状态共同影响;
那么我们设在限制下,当前的以u(这里强调“当前”是因为u在不断移动)为根的子树的最小花费为 val[1](选择u) 和 val[2](不选择u);以及当前的以v为根的子树的 val[3] 和 val[4]。然后在定义一个fval[1~4]分别对应val[1~4],方便转移~
(1)将u移动到与v同层
这里涉及到的变量有 u 对应的状态 val[1],val[2],以及 u 将要移动到的位置对应的状态 fval[1],fval[2]。
假设现在要将u移动到u的第$2^i$个祖先,显然u的状态可以选也可以不选,那么定义a为u的状态:
对于fval[1],这里的“可能不合法的值”是fdp[u][i][a][1](因为不知道是否满足限制),“原有贡献”为dp[u][a],“合法贡献”为val[a](u的状态对应的val值);当然fval[2]也可以类比上面的方法。
(2)将u,v同时移动到lca
和(1)相同,只是多了v也要同时转移~(也就是说还涉及到val[3],val[4])
但是有一种特殊情况——v是u的祖先,这样的话根据v的限制,我们就需要舍去一个val值:
现在的val[1],val[2]也就是lca选/不选所对应的值,但是如果v就是lca,v就会对val产生限制,也就是说当v不能选时,表示选的val[1]就要被舍去,而当v必须选时,表示不选的val[2]就要被舍去。
(3)将lca移动到根节点
完全一样了,这里的lca就代替了u,val[1],val[2]分别指lca选/不选时以lca为根的子树的花费。
最后得到答案就是min(val[1],val[2])
(感觉好难讲懂啊 $QwQ$,不如先看一看代码?)
『源代码』
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~