CF1139C Edgy TreesDFS求连通块大小、思维
题目
给一颗树,每条边都是红或黑的。问有多少种大小为$k$的序列$[a_1,a_2…,a_k]$满足,从$a_1$到$a_2$,从$a_2$到$a_3$… …从$a_k-1$到$a_k$,至少经过一条黑边一次。
题解
只需求出所有只包含红边的连通块大小,然后用所有情况减去只在红色连通块中的情况即可。
所有情况即$n^k$。
不包含黑边的情况:求出的第$i$个只包含红边的连通块大小为$S$,那么这个连通块可以有$S^k$个贡献。
因此,答案就是$n^k-S_1^k-S_2^k…-S_m^k$。
代码
1 | /* |