526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
1702G
Codeforces 1702G2 题解
题目大意 给出一个大小为 \(n\) 的树,\(q\) 次询问,每次给出一个大小为 \(m\) 的点集,判断是否有一条链覆盖这些点(这条链可以经过其他点)。 \(n,\sum m\leqslant 2\cdot 10^5\) , \(q\leqslant 10^5\)。 提示 提示 1 思考将 $m ......
题解
Codeforces
1702G2
1702G
1702
更新时间 2023-10-01
CF1702G2 Passable Paths (hard version)
## 思路 题意:判断是否存在一条链包含树上给定点集。 考虑把 $1$ 当做树的根,将无根树转化为有根树。 考虑这样一个性质:若存在满足条件的最短链,则点集中深度最深的点 $u$ 是该链的一个端点,点集中距离 $u$ 最远的点 $v$ 是该链的另一端点。 >证明:若点 $u$ 不是链的端点,则 $u ......
Passable
version
1702G
Paths
1702
更新时间 2023-07-09
共2篇 :1/1页
首页
上一页
1
下一页
尾页