CF1059E - Split the Tree

一个永远只能在考完后调出 Codeforces 的题的菜鸡厚颜无耻得跑来写题解了。。。

本题要求把树分成的链必须是垂直路径,也就是说不能同时跨越一颗子树的两个根。也就是说每次选中的路径都是到根节点的一串。

所以我们可以通过树上倍增预处理出每个节点 $u$ 如果被选中那么最多可以向上形成长度为 $dp[u]$ 的链。接着跑一遍树上 DP 即可。

预处理时间复杂度 $O(n \log n)$ ,树上 DP 时间复杂度 $O(n)$ 。

貌似因为 D 题比较难调试,做这题的人比较少?反正我这种菜鸡就算考场有时间写了估计也调不出来吧。

这题洛谷的数据太…水,克鲁斯卡尔重构树不连通都可水过。

  • 3545: [ONTAK2010]Peaks
  • 3551: [ONTAK2010]Peaks加强版

在线算法:克鲁斯卡尔重构树套主席树。

在克鲁斯卡尔重构树上维护 DFS 序(或树链剖分)再套上主席树,维护第 $k$ 大。

当然非加强版由于你是重构树(被针对了)可能要大力卡常。比如加个 fread 以及离散化一下什么的。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×