CF1623E题解
Tyyyyyy
·
·
题解
CF1623E
Note：赛场上想的正解没敢写...麻了。
题意简述
给定一棵 n 个节点的二叉树，根为 1 号节点。每个节点上有一个字符 c_i。
定义这棵二叉树的字符表示是以它的中序遍历访问的顺序拼接得到的字符串。
形式化地，设 f(u) 表示以 u 为根的子树的字符表示，则：
f(u)=\begin{cases}\texttt{<empty string>}& \text{if }u = 0 \\ f(l_u) + c_u + f(r_u) & \text{otherwise} \end{cases}
现在，你可以复制一些节点上的字符（即将该节点上的字符 c_u 变为字符串 c_u+c_u），规则如下：
- 每个节点最多被复制一次。
- 一个节点能够被复制，当且仅当它是根节点，或者它的父节点被复制。
- 最多复制 k 个节点。
现在，请你给出在最多 k 次复制后，该二叉树的字典序最小的字符表示。
### 题目分析
我们首先进行一次中序遍历，找到每个节点在中序遍历中所处的位置。
接下来，我们能知道每个节点被复制是否会让字典序更小。只需要对比它和在中序遍历中的下一个和它不同的字符的大小即可。
显然，我们会在能让字典序变小的节点中尽量选择靠前的，即左子树比右子树优先。同时，不难证明：
- 如果当前节点被复制不会使答案更优，则它的右子树一定不会被复制。
- 在左右子树都能使答案更优的前提下，优先复制左子树。
因此，我们可以执行一个 dfs 框架：
- 假设当前访问的节点为 $u$，复制该节点的代价为 $cost$。
- 若 $u=0$ 或 $cost>k$，返回。
- 访问当前节点的左儿子 $l_u$，同时将 $cost\gets cost+1$。
- 如果 $l_u$ 需要被复制，则 $u$ 需要被复制。
- 否则，在 $l_u$ 不需要被复制的情况下，如果 $u$ 被复制能让答案更优，则 $u$ 也需要被复制，且 $k\gets k-cost$。
- 如果当前节点需要被复制，访问当前节点的右儿子 $r_u$，并将 $cost\gets 1$。
这样，我们就找到了每个节点是否需要被复制。时间复杂度 $O(n)$。
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,l[200010],r[200010],pos[200010];
char c[200010];
vector<int>seq;
void precalc(int u)
{
if(l[u])precalc(l[u]);
seq.push_back(u);
if(r[u])precalc(r[u]);
}
bool good[200010],isDup[200010];
void dfs(int u,int cost)
{
if(!u||cost>k)return;
dfs(l[u],cost+1);
if(isDup[l[u]])isDup[u]=1;
else if(good[u])isDup[u]=1,k-=cost;
if(isDup[u])dfs(r[u],1);
}
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",c+1);
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
precalc(1);
char lst=c[seq.back()];
for(int i=n-2;i>=0;i--)
{
int u=seq[i],v=seq[i+1];
if(c[u]!=c[v])lst=c[v];
if(c[u]<lst)good[u]=1;
}
dfs(1,1);
for(auto u:seq)
{
putchar(c[u]);
if(isDup[u])putchar(c[u]);
}
return 0;
}
```