题解 P4654 【[CEOI2017]Mousetrap】

看下面的题意分析时请确保你已经仔细看完了题目。 . . . . 首先这是一个树上博弈问题，好像很复杂，有“弄脏”，“堵塞”，“擦干净”等多种决策，而且些决策还有一堆杂乱无章的限制。 ### 请坚定信念！！！ 出题人也是人，如果这么多限制没有可以转化的地方或共同的性质的话，~~出题人也想不出来~~我们就去吐槽他(~~CEOI??~~) 首先是基于方便起见，把有陷阱的房间设为根。这样老鼠就是在“向上走”，我们写树上倍增，写树链剖分都是这种形式。  给个图(样例)，现在1是根。 我们来试着操作一下，看看能发现什么性质。 由于管理者处于被动地位，还是老鼠比较好想。 设老鼠在4，它有两种决策，向上走(2)和向下走(6,7)。 如果它走入6，4-6就脏了，然后它只能走进8,6-8也就脏了。 然后老鼠就被困住了。 走入7的后果同上。 很快我们发现： ### 一旦老鼠向下进入一个子树内，他最终会被自己弄脏的走廊困在某个叶节点 这时候作为管理者就很舒服了，只要在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净即可。  这是最优决策。证明如下： 首先，老鼠到根节点的路径只有一条，必须走这条路径，也就是说这条路径必须是干净的，所以必须要把走廊擦干净，这才能把老鼠放出来。 也就是说把走廊擦干净的操作数是必要的。 然后还要提前把支路封死，不封支路而让老鼠进去一定不优。 ``` ? | \ 支路 /正 o------o途 / | ? | ``` 左边是支路，支路后面的支路且不论，就算这个支路只有一个节点： ``` | 支路 /正 o------o途 | | ``` 只要耗子钻进去，管理者就必须把路擦干净，至少操作一次，如果支路复杂，想必次数更多。 一开始把支路堵上也是操作一次。 所以干脆把支路堵上算了... 综上所述：把支路堵上是最优决策，把走廊擦干净是必要操作。 最优决策+必要操作=那就一定是最优决策啦 到这里我们证明了： ### 一旦老鼠被困在某个叶节点(前提)，在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净，这是最佳决策。 ------------ 到这里我们已经完成了一半，诸位如果觉得此题不可做或者我没讲清楚，还请继续看。 现在我们有两个结论： 1.一旦老鼠被困在某个叶节点(前提)，在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净，这是最佳决策。 2.一旦老鼠进入一个子树内，他最终会被自己弄脏的走廊困在某个叶节点。 根据(2),老鼠只能向下走入子树一次，然后就只能束手待擒。 ### 3.它的决策便是：向上主动走一些(或不走)，然后找棵子树一头钻进去，然后等待收编。 老鼠走入某棵子树之后需要的操作数，我们可以预处理。 ------------ 具体方法： ### 树形$DP$ 设$f[i]$表示老鼠进入了节点i为根的子树，然后又把老鼠赶回节点i所需要的步数。 (看完状态！！) 还是上面那个图：  | f| 值 | | :| | | 1 | 0 | | 2 | 4 | | 3 | 2 | | 4 | 3 | | 5 | 0 | | 6 | 1 | | 7 | 1 | | 8 | 0 | | 9 | 0 | | 10 | 0 | 可以模拟一下加深理解。 怎么得到f值呢？ 采用数学归纳法的思想，假设我们已经有了节点i的所有子树的f值 ``` i /|\ / | \ 1 2 3 ``` 如果不做干涉，老鼠肯定会钻进f值最大的子树(博弈)。 所以我们把连向f最大的子树的边塞住，老鼠走向次大边。 ### 就是在老鼠向下走之后每次堵住通向f值最大的子树的边。 上面的方案对吗？ 好像最大边的f与次大边的f相等时，就多塞了一下？？ NO,没有多塞，~~早塞晚塞都得塞~~。 ``` i /|\ / | \ 1 2 3 ``` 假设上图的$f[1]=66;f[2]=233;f[3]=233$ 我们先堵住2： ``` i /|\ / x \ 1 2 3 ``` 老鼠走向3，经过一番周折(~~233~~)以后，又被赶回了3. ``` i /|\脏 / x \的 1 2 3 ``` 我们要把i-3这条边擦干净...欸？老鼠又钻进i-1了，~~啊啊啊啊~~ 所以说i通向子树的路径，我们要么擦干净，要么堵住(堵住一定优，参考（1）的证明)。 每条通向子树的路径都要耗掉一个操作，不如先把其中一个先做了，堵住通向f值最大的子树的边，还顺便能减小答案(感性理解一下)。 总结一下： ### 4.在老鼠向下走之后(前提)每次堵住通向f值最大的子树的边，一定最优。 dp方程 $f[i]=f[son\ \ of\ \ i]$的次大值$+i$的度数$-1$ 注： - $-1$ 是因为$i$和他爸爸之间有一条边不需要考虑。 - 如果只有一棵子树，次大值为0. 边界 叶节点和根节点的f值为0。 树形DP完毕！！ ------------ 现在我们有四个结论： 1.一旦老鼠被困在某个叶节点(前提)，在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净，这是最佳决策。 2.一旦老鼠进入一个子树内，他最终会被自己弄脏的走廊困在某个叶节点。 3.耗子决策只能是：向上主动走一些(或不走)，然后找棵子树一头钻进去，然后等待收编。 4.在老鼠向下走之后(前提)每次堵住通向f值最大的子树的边，一定最优。 ### 结合1,4；只要我们知道老鼠钻进了哪棵子树，我们就能$O(1)$求出钻进了子树情况下的最优解。 具体的来说，就是还要预处理$sm[i]=i$结点到根的路径旁边的支路数量 （注：$sm[i]$与程序中的sm[i]不是一个意思） 然后就能算出$hh[i]=$老鼠向下一条边来到i,然后需要的最少步数。 ### $hh[i]=sm[father[i]]+f[i]-(father[i]!=$老鼠开始时的结点$)$ 这里的“$-(father[i]!=$老鼠开始时的结点$)$”是因为老鼠在向上走的过程中把边弄脏了，弄脏的边就不用堵了。而如果老鼠没有向上走$(father[i]==$老鼠开始时的结点$)$那么就不用-1. ``` (就相当于) f[i]--; if(father[i]==老鼠开始时的结点)f[i]++; ``` 还记得(3)耗子决策只能是：向上主动走一些(或不走)，然后找棵子树一头钻进去，然后等待收编。 现在问题来了：老鼠究竟会选择钻进那个子树？？ ------------ 好像很麻烦，我们考虑二分答案转化为判定性问题。 设check(k)表示花费k不能不能把老鼠赶入陷阱。 假设老鼠知道了管理者的这个目标，它只要随便找个$hh[i]>k$的子树钻进去,管理者就会TLE。 所以要把$hh[i]>k$的子树全部封死，如果管理者的手速不够快(一回合只能操作一次)，老鼠就会钻进某个$hh[i]>k$的子树，$return\ 0;$ 注意在封堵$hh[i]>k$的子树时也需要操作数，所以k会不断减小。 如果封堵的总次数>k，也就是k变成了负数，也要$return\ 0;$ 看核心代码： ```cpp //s数组按顺序(老鼠->根)存的是老鼠开始时的结点到根路径上的所有节点 bool check(int k) { int sum=0,tmp; //有这个tmp的缘故是因为在j的循环内k--会WA，同一个结点的子树的k要求必然相同(感性理解，谢谢) for(int i=1;i<top;i++){ tmp=0; for(int j=0;j<g[s[i]].size();j++){ int v=g[s[i]][j];//某棵子树 if(v!=s[i+1]&&//往上走的情况不在这里考虑,应该在下一次循环 v!=s[i-1]&&//不能走回头路 sm[i]+f[v]+1-(i!=1)>k)//不堵上就会TLE tmp++;//堵上 }sum+=tmp;k-=tmp;//操作次数增加，剩余操作次数减少 if(k<0||//封堵的总次数>k sum>i)//管理者的手速不够快 return 0; }return 1; } ``` 完毕，此题完结。 ------------ 几个坑点： 1.该题目中有两个数据是一条链(可深了)。 2.有一个数据耗子直接出现在陷阱房。 我没有加特判就过了。 代码： ```cpp #include<cstdio> #include<vector> using namespace std; //令 f_i 表示耗子从这个节点进入子树后又把把耗子赶回来的最小步数 //取次大儿子转移，因为可以把通往 wi 最大的儿子的路封上， //耗子就会走向次大儿子。 int m,n,from,to,root,oo,sm[1000500],s[1000500],top, f[1000500],du[1000500],fa[1000500]; vector<int> g[1000500]; bool e[1000500],asd; void dfs(int num,int last) { fa[num]=last;//还顺便处理了一个fa数组 if(du[num]==0){f[num]=0;return ;}//边界 int h1=0,h2=0;//h1:最大值; h2:次大值 for (int i=0;i<g[num].size();i++) if (g[num][i]!=last){ dfs(g[num][i],num); if (f[g[num][i]]>=h1)//注意等于号 {h2=h1;h1=f[g[num][i]];} }f[num]=h2+du[num]-1; } //s数组按顺序(老鼠->根)存的是老鼠开始时的结点到根路径上的所有节点 bool check(int k) { int sum=0,tmp; //有这个tmp的缘故是因为在j的循环内k--会WA，同一个结点的子树的k要求必然相同(感性理解，谢谢) for(int i=1;i<top;i++){ tmp=0; for(int j=0;j<g[s[i]].size();j++){ int v=g[s[i]][j];//某棵子树 if(v!=s[i+1]&&//往上走的情况不在这里考虑,应该在下一次循环 v!=s[i-1]&&//不能走回头路 sm[i]+f[v]+1-(i!=1)>k)//不堵上就会TLE tmp++;//堵上 }sum+=tmp;k-=tmp;//总操作次数增加，剩余操作次数减少 if(k<0||//封堵的总次数>k sum>i)//管理者的手速不够快 return 0; }return 1; } int main() { scanf("%d%d%d",&n,&root,&m); for (int i=1;i<n;i++){ from=i;to=i+1; scanf("%d%d",&from,&to); g[from].push_back(to); g[to].push_back(from); du[from]++;du[to]++; }dfs(root,0); f[root]=0;//边界 for(int i=m;i;i=fa[i])s[++top]=i; for(int i=top-1;i;i--)sm[i]=sm[i+1]+du[s[i]]-1-(s[i]!=root); int l=0,r=1e8,mid; while(l<r){ mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1;//二分,这里要+1 }printf("%d",r); return 0; } ``` 丑点请见谅