大佬的思路:
#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;
}
View Code
后记:
- 他本身就是要中序后的一个字典序的大小
- 于是看看中序排序后的序列是什么, 然后根据这个序列看看那个点是不是需要复制 (比后面第一个不同的数小)
- 在上面预处完后开始dfs, 更具字典序性子
- 左边优先级最高,然后就是中间吗,在是右边,
- 注意这个是更新时的前提时父亲也要加倍, 所以中间不行时,右边一定也不行
题目分析
我们首先进行一次中序遍历，找到每个节点在中序遍历中所处的位置。
接下来，我们能知道每个节点被复制是否会让字典序更小。只需要对比它和在中序遍历中的下一个和它不同的字符的大小即可。
显然，我们会在能让字典序变小的节点中尽量选择靠前的，即左子树比右子树优先。同时，不难证明：
- 如果当前节点被复制不会使答案更优，则它的右子树一定不会被复制。
- 在左右子树都能使答案更优的前提下，优先复制左子树。
因此，我们可以执行一个 dfs 框架：
- 假设当前访问的节点为 �u，复制该节点的代价为 ����cost。
- 若 �=0u=0 或 ����>�cost>k，返回。
- 访问当前节点的左儿子 ��lu，同时将 ����←����+1cost←cost+1。
- 如果 ��lu 需要被复制，则 �u 需要被复制。
- 否则，在 ��lu 不需要被复制的情况下，如果 �u 被复制能让答案更优，则 �u 也需要被复制，且 �←�−����k←k−cost。
- 如果当前节点需要被复制，访问当前节点的右儿子 ��ru，并将 ����←1cost←1。
这样，我们就找到了每个节点是否需要被复制。时间复杂度 �(�)O(n)。
标签：cost,int,中序,dfs,复制,CFD2E,节点 From： https://www.cnblogs.com/Lamboofhome/p/17196699.html