ARC157E XXYX Binary Tree 题解
2024-09-18 17:41:59
首先，条件可以抽象为 Y 不能相连，然后：
- 钦定根为
Y，YX的个数加上 \(2\)； - 钦定某一个叶子节点为
Y，XY的个数加上 \(1\)； - 钦定某一个非叶子非根节点为
Y，YX的个数加上 \(2\)，XY的个数加上 \(1\)；
根据上面的讨论，YX 的个数一定为偶数，先判掉。
现在问题变成了一个二维的类独立集问题，直接设计 \(f_{u,i,j,0/1}\) 表示 \(u\) 的子树选出一个独立集填 Y 满足 XY 和 YX 个数分别为 \(i,j\) 是否可行，\(u\) 选或者不选。
这个 DP 显然不能过，我们考虑优化。
讨论根是否选，现在变成只有两类物品，并且两类物品对于 XY 的贡献是相同的，设计 \(f_{u,i,0/1}\) 表示 \(u\) 内部的子树选出 \(i\) 个叶子填 Y，能选出来的最大独立集，根据 \(f\) 数组的值可以直接判断是否可以满足条件。
总时间复杂度是 \(O(n^2)\) 的，证明方法是考虑每一对叶子都会被枚举一次。
最新文章
- swift开源项目精选
- Linux 引导修复
- POJ2976 Dropping tests（01分数规划）
- js事件冒泡和事件委托
- memcached全面剖析--4
- angular.js的post数据方式
- Egret 纹理、计时器
- IDL 计算TVDI
- vr & obv
- 【Unity Shaders】Reflecting Your World —— Unity3D中简单的Cubemap反射
- Python IO密集型任务、计算密集型任务，以及多线程、多进程
- H5外包团队 android视频压缩，使用ffmpeg方案
- 【repost】js window对象属性和方法相关资料整理
- jquery 上下滚动显示隐藏
- JAVA多线程17个问题
- 彻底关闭win10后台同步数据（转自技术社区）
- electron 使用 node-ffi 调用 C++ 动态链接库（DLL）
- linux下网络查看命令ss
- Antd前端开发采坑记录
- poj_2553 强连通分支&出度为0的点