| 题目名称 | 2437. [HZOI 2016] 暗之链锁 II |
|---|---|
| 输入输出 | yamtwo.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Hzoi_
于2016-08-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：33， 通过率：36.36% | ||||
 ┭┮﹏┭┮ |
100 | 0.420 s | 13.46 MiB | C++ |
 rewine |
100 | 0.577 s | 11.53 MiB | C++ |
 Anonymity |
100 | 0.745 s | 9.85 MiB | C++ |
 AntiLeaf |
100 | 1.293 s | 5.11 MiB | C++ |
 MistyEye |
100 | 1.322 s | 8.33 MiB | C++ |
|
AntiLeaf |
100 | 1.334 s | 5.75 MiB | C++ |
 Hzoi_ |
100 | 1.401 s | 5.75 MiB | C++ |
 _Itachi |
100 | 2.131 s | 6.39 MiB | C++ |
 洛克索耶夫 |
100 | 2.259 s | 23.19 MiB | C++ |
|
哒哒哒哒哒！ |
100 | 2.291 s | 16.20 MiB | C++ |
| 关于 暗之链锁 II 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
树链剖分 + 组合数
另外 数据不保证不出现重边和自环。什么鬼?! | ||||
|
垃圾出题人......样例忘了改了
AntiLeaf
2016-08-20 08:34
7楼
| ||||
|
来一发题解
AntiLeaf
2016-08-20 08:10
6楼
| ||||
|
嗯...感谢@magic_sheep 给我的灵感......
等等...尼玛把标程写错了，垃圾出题人= = Hzoi_
2016-08-16 10:27
5楼
| ||||
|
标程错了！！！！
数据是用标程生成的，也错了！！！ _Itachi
2016-08-16 10:26
4楼
| ||||
|
平时我是不发表评论的
 Hzoi_Yniverse
2016-08-15 14:45
3楼
| ||||
|
AntiLeaf
2016-08-15 06:29
2楼
| ||||
|
_Itachi
2016-08-15 06:26
1楼
| ||||
小e【题目描述】
传说中的暗之链锁被人们称为Dark。Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现Dark呈现无向图的结构，图中有n个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有n–1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有m条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断Dark的k条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你切断一条主要边和不足k条附加边之后就已经把Dark斩为两截，你也需要再切够k条附加边才算击败了Dark。
由于方案数可能很大，你只需要输出方案数模1000000007($10^9+7$)的值。
【输入格式】
第一行包含三个整数n,m,k。
之后n–1行，每行包括两个整数x和y，表示x和y之间有一条主要边。
之后m行以同样的格式给出附加边。
【输出格式】
输出一个整数表示答案。
【样例输入】
5 3 2 1 2 4 5 3 2 1 4 1 3 5 2 3 4
【样例输出】
4
【样例解释】
可能的方案为
(4,5)+(1,3)+(2,5)
(4,5)+(2,5)+(3,4)
(1,4)+(2,5)+(3,4)
(2,3)+(1,3)+(3,4)
(每种方案第一个是主要边，其余是附加边)
【数据范围】
对于20%的数据，n≤1000，m≤1000。
对于另20%的数据，k≤2。
对于100%的数据，n≤100000，m≤200000，0≤k≤m。
数据不保证不出现重边和自环。
【提示】
没啥提示
【来源】
HZOI 2016