树形dp,3天搞定
A - Information Disturbing
题意
对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求
- 每条边带权重,切掉的边权重和不大于$m$
- 切掉的每条边都不能大于一个$ans$
问$ans$最小是多少?
题解
二分+树形dp
+1 ans初始化-1
看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断
1 | if(G[head[u]].to == father) |
对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求
问$ans$最小是多少?
二分+树形dp
+1 ans初始化-1
看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断
1 | if(G[head[u]].to == father) |
给一颗树,已知每个点有权值和陷阱,你不能往回走,如果走过$c$个陷阱或者无路可走就结束,可以从任一点开始走,问能获得多少权值。
树形dp。
$dp[i][j][0/1]$是在以$i$为终点,经过$j$个陷阱,$1$代表起点有陷阱,$0$代表起点没有陷阱。
转移方程
答案就是枚举每个根节点中子树进入和出去,特判一下链的组成
心路历程:我一开始想的是二维dp转移方程,但是只能对一个根节点求值,因为子节点也有可能走根节点那条路径,没有想到树形dp对于求解问题这么灵活,答案不一定一定是dp数组中的元素,而可以是通过拼接数组中元素来构成答案。而且我想法是从根节点走到叶子节点,而不是从子树节点出发到根节点,还是too young啊。之后我拼接了自己的垃圾二维dp,发现因为在迷宫中你碰到$c$个陷阱之后就不能走了,但是我这个二维数组不能转移方程。我两条链拼接的时候会多加几个节点,因为左右两个链如果加起来为$c$之后,其中一条链到了trap点,就不能再走了。所以才要三维数组。
1 |
|
每个人拥有一个信息,也可以传给另外一个人他拥有的所有信息。现在给定一个联络树,问至少多少次传递可以让所有人拥有所有信息。
可以看出至少要$(n-1)*2$次传递,因为每个人都至少传出一次,传入一次。而怎么可以最少传递呢?我们可以假设根为中心,先将所有信息传递给他,之后再从他传递回来。这里有一点很巧妙,传入和传出的可能种类是一样的,所以我们只需要计算一次传入,平方后便是该点为中心的方案数。
因为子节点必须先传给父节点信息以免漏传,所以传入的方案数是满足一种拓扑排序的。那么可以看我之前的一篇博客,计算拓扑排序对一个点进行计算的。
那么怎么从已知的父节点的$f(root)$传递到子节点$f(v)$呢?
$s(i)$表示以$i$为根节点的子节点数目。
我们假设子节点$s(v)=q$,那么如果子节点变成根节点后,子节点的$s(v)=n$,而原来的父节点$f(u)$变成了$n-q$个子节点数目了。于是通过公式
$f(root)=(f(root)-1)!/s(1)/s(2)/…/s(n)$
我们可以推导出$f(v) = f(u) * s(q)/s(n-q)$
搞定!
1 |
|
给定$n-1$组关系,节点$a$不能站在节点$b$的前面,使得$n$站成一行,问有多少种站法。
树形dp + 组合数学
我们可以这样想像,假设拓扑排序是不存在的,这些点的排序忽略,那么点可以看做是同样颜色的点,那么$x_1,x_2$个数的点排列的排列数为$(x_1+x_2)! /(x_1! * x_2!)$。而这些点其实是不一样的,他们有自身的拓扑排序顺序,于是答案就是$f(x_1) f(x_2) (x_1+x_2)!/(x1! * x_2!)$。
简单写一下从递推到通向。$c_i$表示是$root$的子节点,$s(i)$表示$i$节点的子节点数。
$f(root) = f(c1)f(c2)…f(c_k)*((s(root)-1)!/s(c_1)!/s(c_2)!/…/s(c_k)!)$
$f(c_1)=f(x_1)f(x_2)…f(x_z)*((s(c_1)-1)!/s(x_1)!/s(x_2)!/…/s(x_z)!)$
$s(c_1)和s(c_1-1)$可以约掉。而且到叶子节点$f(x_1)$都变成$1$了$s(x_1)$也变成了0.
$f(root)=(s(root)-1)!/s(1)/s(2)/…/s(n)$
1 |
|
Reference:https://blog.csdn.net/xiao_k666/article/details/78609562