D156 *【树上边差分】删2边使树不连通[闇の連鎖]
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
0x60图论（0x63 树的直径与最近公共祖先）例题3：暗的连锁[POJ3417]
题目描述
有一棵有 个点 条原始边的树。为了增强树上节点的连通性，另外增加 条附加边。问题：选择切断其中两条边（需要刚好是：一条原始边 + 一条附加边），让树成为不连通的两部分，求一共有多少种不同的方案。
输入格式
第一行包含两个整数 和 ； 之后 行，每行包括两个整数 和 ，表示 和 之间有一条原始边； 之后 行以同样的格式给出附加边。
输出格式
输出一个整数表示答案。
输入输出样例
输入 #1
4 1
1 2
2 3
1 4
3 4
输出 #1
3
数据范围与提示
对于 的数据，；
对于 的数据，。数据保证答案不超过 。
提高8.5（RMQ+最近公共祖先LCA）
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 18
- 开始于
- 2024-8-1 23:00
- 结束于
- 2024-8-10 3:00
- 持续时间
- 196 小时
- 主持人
-
admin
- 参赛人数
- 17