主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1156D 0-1-Tree
最后更新于 2025-08-28 08:55:54
作者
2huk
分类
题解
题解
CF1156D
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
这有蓝？最开始还是紫？建议降黄/绿。 显然一条路径合法等价于前面只走 $0$ 边后面只走 $1$ 边。不妨枚举转折点。 令其为 $x$。现在我们要求有多少 $u, v$ 使得 $u \sim x$ 路径上的边都是 $0$，$x \sim v$ 路径上的边都是 $1$。 显然可以分别求然后乘法原理。以求 $u$ 的数量为例。 注意到，合法的 $x$ 在树上一定是一个连通块，且这个连通块内的边都是 $0$。于是可以开一个并查集，维护这样的全 $0$ 边连通块。那么统计 $x$ 的数量就很简单了。 注意题目中路径 $(u, v)$ 需要保证 $u \ne v$。所以答案还要减 $n$。 代码：<https://codeforces.com/contest/1156/submission/289097972>
正在渲染内容...
点赞
0
收藏
0
