当前位置:首页 > 动态规划 > 树形DP > 正文
洛谷P8867建造军营(NOIP2022)
156+

题目大意:n个点m条边,请至少选择1个点建造军营,要求军营之间的唯一路径必须看守,其他道路无要求。请问有多少中建造军营的方案?(所选军营、看守道路不一样即不同方案)

题目描述

A 国与 B 国正在激烈交战中,A 国打算在自己的国土上建造一些军营。

A 国的国土由 $n$ 座城市组成,$m$ 条双向道路连接这些城市,使得任**意两座城市均可通过道路直接或间接到达**。A 国打算选择一座或多座城市(**至少一座**),并在这些城市上各建造一座军营。

众所周知,军营之间的联络是十分重要的。然而此时 A 国接到情报,B 国将会于不久后袭击 A 国的一条道路,但具体的袭击目标却无从得知。如果 B 国袭击成功,这条道路将被切断,可能会造成 A 国某两个军营无法互相到达,这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路(**可以是一条或多条,也可以一条也不看守**),A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案,使得 B 国袭击的无论是 A 国的哪条道路,都不会造成某两座军营无法互相到达。现在,请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多,你只需要输出其对 $1,000,000,007\left(10^{9}+7\right)$ 取模的值即可。两个方案被认为是不同的,当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有,或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

输入输出格式

输入格式

第一行包含两个正整数 $n,m$,分别表示城市的个数和双向道路的数量。

接下来 $m$ 行,每行包含两个正整数 $u_{i},v_{i}$,描述一条连接 $u_{i}$ 和 $v_{i}$ 的双向道路。保证没有重边和自环。

输出格式

输出一行包含一个整数,表示建造军营和看守道路的方案数对 $1,000,000,007\left(10^{9}+ 7\right)$ 取模的结果。

输入输出样例

输入样例 #1

2 1
1 2

输出样例 #1

5

输入样例 #2

4 4
1 2
2 3
3 1
1 4

输出样例 #2

184

输入样例 #3

见附加文件里的 barrack/barrack3.in

输出样例 #3

见附加文件里的 barrack/barrack3.ans

输入样例 #4

见附加文件里的 barrack/barrack4.in

输出样例 #4

见附加文件里的 barrack/barrack4.ans

说明

### 样例 1 解释

A 国有两座城市,一条道路连接他们。所有可能的方案如下:

– 在城市 $1$ 建军营, 不看守这条道路;
– 在城市 $1$ 建军营, 看守这条道路;
– 在城市 $2$ 建军营, 不看守这条道路;
– 在城市 $2$ 建军营, 看守这条道路;
– 在城市 $1,2$ 建军营, 看守这条道路。

### 数据规模与约定

对所有数据,保证 $1 \leq n \leq 5 \times 10^5$,$n – 1 \leq m \leq 10^6$,$1 \leq u_i, v_i \leq n$,$u_i \neq v_i$。

各测试点的信息如下

|测试点编号 | $n \leq $ | $m \leq $| 特殊条件 |
| :-: | :-: | :-: | :-: |
| $1 \sim 3$ | $8$ | $10$ | 无 |
| $4 \sim 7$ | $16$ | $25$ | 无 |
| $8 \sim 9$ | $3000$ | $5000$ | 无 |
| $10 \sim 11$ | $5 \times 10^5$ | $10^6$ | 特殊性质 $\mathrm{A}$ |
| $12 \sim 14$ | $5 \times 10^5$ | $10^6$ | $m = n – 1$ |
| $15 \sim 16$ | $5 \times 10^5$ | $10^6$ | $m = n$ |
| $17 \sim 20$ | $5 \times 10^5$ | $10^6$ | 无 |

特殊性质 $\mathrm{A}$:保证 $m=n-1$ 且第 $i$ 条道路连接城市 $i$ 与 $i+1$。

解题思路

暴力做法:暴力枚举每个点是否建造军营,对于每一条边,判断不经过他能否从一个军营通向其他军营,如果可以那么他是否看守都可以,方案乘以2。

链的做法:枚举建造军营最左边和最右边,中间的边必须看守,外面的边是否看守都可以;优化枚举对象,只枚举最远两个军营的距离即可O(n)实现。

两个部分分加起来有5*9=45分!!!

正解:将图缩点转成一棵树,树上跑树形DP即可。

程序实现


(感谢huangjianheng提供思路)

报歉!评论已关闭.