考虑有解当且仅当所有叶子能到的点集有交。
不难证明交是连通块，点减边 Trick。
接下来需要数所有点能到 $x$ 的方案，转化成数一个集合的点到不了 $x$ 的方案。
容斥一下哪些叶子到不了 $x$，那么唯一不能要的边就是两个不同子树中到不了 $x$ 的叶子。
这样可以做到 $O(n^3)$，能不能更进一步呢？
考虑定根之后只考虑子树内的叶子，子树外必须连通的方案可以求出，于是就 $O(n^2)$ 了。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #123 for Problem #8001. 公交线路
Type: Editorial
Status: Open
Posted by: dXqwq
Posted at: 2025-12-12 23:12:33
Last updated: 2025-12-12 23:12:40
题解
Comments
No comments yet.