526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
7165
题解 P7165 [COCI2020-2021#1] Papričice
传送门。 题意 有一棵树,可以断掉 \(2\) 条边,会形成三个连通块,求三个连通块中大小最大减最小的最小值。 分析 我们观察两条边之间的关系,分类考虑: 两条边成祖孙关系。 两条边没有祖孙关系。 首先,我们肯定我们的大方向,固一动一(说起来为什么想到了数学题),先固定一条边,再在其他边中取得最适合 ......
题解
P7165
Papri
7165
2020
更新时间 2024-01-01
题解 P7165 [COCI2020-2021#1] Papričice
### 题面描述 给定一颗树,求分成三部分后的最小差异值。 ### 题解 暴力:每次枚举两个点,将其父边断掉,如果存在祖先关系则特判一下,复杂度 $O(n^2)$,预计 50pts。 正解:dfs 搜索每个结点,砍掉它的父边,剩下的尽量等分(易证)。 这一步可以用 multiset 维护。 对于一个 ......
题解
P7165
Papri
7165
2020
更新时间 2023-07-17
共2篇 :1/1页
首页
上一页
1
下一页
尾页