708

传送门 description 给定 \(n,m,P,k\)。一个 \(n+2\) 行 \(m\) 列的网格图第 \(2\) 至 \(n+1\) 行每秒每行左右两端的方格都有 \(P\) 的概率消失。求 \(k\) 秒后第一行和最后一行联通（上下左右四个格子联通）的概率。 \(n,m\leq 1.5 ......

对于一个不是重心的点 \(u\)，它必定有一棵子树 \(T\) 包含所有重心（如果有两个重心则它们必定相邻），显然 \(|T|>\lfloor\frac{n}{2}\rfloor\)，这阻碍了它成为重心。贪心地想，我们要在 \(T\) 中找出一棵子树 \(S\) 使得 \(|S|\leq\lfloo ......

CF708C Centroids 一道换根 DP。 我们可以先找出树的一个重心，那么对于其他所有不是重心的点，它不能成为重心时因为它父亲的那一支节点数大于一半，而可以改造成功，则意味着可以在他父亲那一支里，可以找到子树u，使 $siz[u] \le n/2 && siz[fa]-siz[u] \le ......

题意： 给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。 请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于$\dfrac{n}{2}$，则称某个点为重心） 思路： 是今天遇到的一道有意思的换根dp呃呃。 从题意来看 ......

感觉 这篇题解 的做法很强啊，贺一下。 连通：考虑将每一种情况对应一条路径。钦定这条路径为能往下则往下，不能往下就向左或向右走到第一个能往下的位置然后往下。 这样只考虑每一种路径，再对应的计算路径相应的情况的概率和。这个是容易计算的，而路径需要记录的状态少了一维，于是就可以 $O(nm)$ 的解决了 ......