Description

给一棵 $n+1$ 层的完全二叉树（共 $2^{n+1}-1$ 个结点，$2^n$ 个叶子），结点从上到下，从左到右编号为 $1\sim 2^{n+1}-1$，每个非叶结点有一个激活代价 $w_i$，每个叶子有一个权值 $q_i$，所有 $q_i$ 构成 $1\sim 2^n$ 的排列。Alice 和 Bob 在这棵树上玩游戏，Alice 可以用不超过 $K$ 的代价激活一些结点，随后 Bob 会对这棵树进行 dfs。对于 Alice 激活的结点，Bob 必须先走左儿子再走右儿子；其余时候，Bob 可以任意决定 dfs 顺序。

按照 Bob 访问叶子的顺序将所有 $q_i$ 排成序列 $Q$，Alice 希望 $Q$ 的字典序最大，Bob 希望 $Q$ 的字典序最小，问最终的 $Q$ 是什么。

$T$ 组数据。

$1\le T\le 100,1\le n\le 16,1\le \sum 2^n\le 10^5,0\le K\le10^{12},0\le w_i\le 10^{12}$

Read More

关于树上背包的上下界优化，当时 fz 推荐我读的是 ouuan 的文章（cnblogs github pages），但是，我现在认为那里面的复杂度证明存在问题。

Read More

Description

给出一棵有 $n$ 个节点的树，每个节点有一个权值 $a_i$，求出不相交的两条链的最大权值和。

Read More