PBL 赛时 T6 求解

题目总版

wangziwenhk @ 2024-11-21 21:48:02

大致题意：

完美序列的定义：

给你一颗无根树，其中有黑边和红边，求该树中完美序列的数量。

输入：

输入两个正整数 n,k，其中 n 表示无根数的节点数量，k 是一个完美序列的长度（见上）

接下来 n-1 行 u_i,v_i,d_i 分别表示一条边与这条边的颜色，d_i=0 是红色，d_i=1 是黑色

输出：

完美序列的数量对 10^9+7 取模

样例

样例输入

4 4
1 2 1
2 3 1
3 4 1

样例输出

252

数据范围

对于 100\% 的数据：

  • 1 \le n,k \le 10^5
  • 1 \le u_i,v_i \le n
  • d_i \in 1,0

by wangziwenhk @ 2024-11-21 21:53:55

我的思路是构建一个以 1 为根的树然后求所有边为红色的子树的大小计算它的贡献。

完美序列的总个数有 n^k 个，自身的点而永远不能经过任何边的序列有 n 个，每个子树不能产生序列的有 size^k 个，但是由于和第一个贡献冲突了所以要减去 size 个

@Fa_Nanf1204 说是跑连通块，但是我觉得我这个子树做法也是正确的，但是赛时 WA 了，有人指出我哪里错了吗

by csxx601cjy @ 2024-11-21 21:54:01

原来你也参加了PBL。这题我也不会，但输出 0 能骗 10 分。

by wangziwenhk @ 2024-11-21 21:58:40

@csxx601cjy 我知道，直接 n^k -n 可以骗分

by csxx601cjy @ 2024-11-21 22:05:08

@wangziwenhk

https://www.luogu.com.cn/discuss/1001531

|