题目名称 | 4078. 路径覆盖 |
---|---|
输入输出 | lucover.in/out |
难度等级 | ★★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 10 |
题目来源 | yuan 于2024-11-26加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:1, 提交:2, 通过率:50% | ||||
xxz | 100 | 0.339 s | 14.90 MiB | C++ |
徐诗畅 | 30 | 6.331 s | 4.28 MiB | C++ |
本题关联比赛 | |||
20241129 |
关于 路径覆盖 的近10条评论(全部评论) |
---|
敢问 $NOIP$ 之路在何方?路在脚下。
有棵 $n$ 个点的无根树,小小想用若干路径覆盖所有边,且保证任意一条边恰被覆盖一次。
“奇数度点数除以 $2$”——小 $A$ 同学脱口而出。既然这题已经被秒了,小小只好重新出一道题。
你可以使用下面 $2$ 种操作来覆盖所有边,且保证任意一条边恰被覆盖一次:
1.选择一条路径 $(u,v)$ ,覆盖路径上的每一条边(前提是路径上所有边都没有被覆盖);
2.选择一个点 $u$ ,覆盖与 $u$ 相连的所有边(前提是与 $u$ 相连的所有边都没有被覆盖);
有 $q$ 次独立询问:每次首先指定一个点 $x$ 进行操作 $2$,求最小化操作次数(即输出覆盖剩下的森林所需的最小操作次数$+1$)。
第一行输入两个整数 $n,q$。
接下来 $n-1$ 行,每行 $2$ 个整数 $(u,v)$ 代表一条边。
最后一行,包含 $q$ 个整数$x$,代表询问。
输出 $q$ 行,每行 $1$ 个整数代表答案。
5 5 3 1 1 4 4 5 5 2 1 2 3 4 5
2 2 2 3 2
5 5 1 2 2 3 2 4 1 5 1 2 3 4 5
2 2 2 2 2
5 5 1 2 1 3 1 4 3 5 1 2 3 4 5
2 2 2 2 2
5 5 1 2 2 3 2 4 2 5 1 2 3 4 5
3 1 3 3 3
点击下载样例5