Educational Codeforces Round 47 F

未分类

题目:
给定一个有根树,对每个节点,求其宽度及其对应的深度,宽度一样时要求深度最小.
宽度的定义是对同一个深度的最多的子节点的个数.

题解:
考虑启发式合并,对每个节点维护一个数据结构$d_u$,$d_u[i]$表示以$u$为根节点的子树,深度为$i$的节点的个数,显然启发式合并可做,对于每个节点,$dfs$处理各个子树之后,把小子树暴力合并到最大的子树中,需要维护以下的操作:
1.在$d_u$前面添加一个元素,值是$1$.
2.顺序访问$d_u$的全部元素,并修改.
3.对$d_u$进行$resize$操作,并且只增不减.
$C++$中的$list$库可以完美支持以上操作.
时间复杂度为$O(nlogn)$.

$AC$ $code$:http://codeforces.com/contest/1009/submission/40365078