| 题目名称 | 2434. 暗之链锁 |
|---|---|
| 输入输出 | yam.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 9 |
| 题目来源 |
 Magic_Sheep
于2016-08-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：132， 提交：309， 通过率：42.72% | ||||
 Theresis |
100 | 0.223 s | 12.13 MiB | C++ |
 Hallmeow |
100 | 0.242 s | 12.13 MiB | C++ |
 Anonymity |
100 | 0.246 s | 4.10 MiB | C++ |
|
Hallmeow |
100 | 0.249 s | 12.13 MiB | C++ |
|
Hallmeow |
100 | 0.265 s | 12.13 MiB | C++ |
 Hzoi_QTY |
100 | 0.269 s | 3.21 MiB | C++ |
|
嗨嗨嗨 |
100 | 0.278 s | 13.38 MiB | C++ |
 Hzoi_Hugh |
100 | 0.284 s | 6.51 MiB | C++ |
|
Hzoi_Hugh |
100 | 0.289 s | 6.51 MiB | C++ |
 Hale |
100 | 0.293 s | 37.69 MiB | C++ |
| 关于 暗之链锁 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
lca+树上差分，lca用的是树上倍增法
| ||||
|
B了个狗，拍了将近3000组数据，在树剖里找到无数小错误
 瑆の時間~無盡輪迴·林蔭
2019-09-02 08:19
24楼
| ||||
|
回复 @Hzoi_Hugh :
草拟吗。骂我干嘛。。。 Hallmeow
2017-07-26 19:28
23楼
| ||||
|
回复 @Hallmeow : 草泥马
| ||||
|
成功水到rank1，而且还是暴力lca。。。
| ||||
|
回复 @天亮说晚安· :
同意 Hzoi_QTY
2017-07-26 14:06
20楼
| ||||
|
暴力修改就行
| ||||
|
跑的好慢
--update-- 树状数组比线段树快好多= = | ||||
|
下放边权，应该是在lca减两次。。。我简直智障
| ||||
tat
天亮说晚安·
Hzoi_Mafia
Troywar
Magic_Sheep【题目描述】
传说中的暗之连锁被人们称为Dark。Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现Dark呈现无向图的结构，图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N – 1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断
Dark的一条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你第一步切断主要边之后就已经把Dark斩为两截，你也需要切断一条附加边才算击败了Dark。
【输入格式】
第一行包含两个整数N和M。
之后N – 1行，每行包括两个整数A和B，表示A和B之间有一条主要边。
之后M行以同样的格式给出附加边。
【输出格式】
输出一个整数表示答案。
【样例输入】
4 1 1 2 2 3 1 4 3 4
【样例输出】
3
【提示】
自己瞎做吧
【数据范围】
对于20% 的数据，N≤100，M≤100。
对于100% 的数据，N≤100 000，M≤200 000。数据保证答案不超过2^31– 1。