题解 P5597 【【XR-4】复读】

· · 题解

这题思维挺新颖的，一时候拿到还真不一定做出来，本人也是看了讲评才明白的，真是让人叹为观止。

可惜的是，很多人表示并不明白官方题解是啥意思，故写文以记之，希望可以帮助更多人。

首先我们要明白题目的意思：给定一个无限二叉树，并给定以1号节点为根标记一个小的染色二叉树，找一个最小遍历循环节（以下简称，S）可以通过无数次循环走遍这个染色二叉树（以下简称，T）。

由于二叉树的大小是无限的，所以可以保证如果S合法（即不会跑到根的父亲），就可以一直走下去。当然，如果出现遍历到的节点\notin T，这并不影响循环节的合法性。

我们来考虑正解。很明显的是，每复读一遍S，你一定仅会到达当前节点子树中的某一节点。当该节点 \notin T 时，你之后一定会越偏越远，再也遍历不到T的节点了，整个复读就此结束。而我们要做的，就是确保我们构造的S可以在此之前遍历完T的所有节点。

又由于每次复读一遍S，所到达节点x 与 当前节点now 的相对位置是不变的，而且下一步我们也仅会遍历x子树中的元素了，这就意味着我们要遍历到所有p\in T，且p属于now的子树但不属于x的子树，这些点若此时不被遍历就永远没机会了。

基于以上两点，我们不妨通过枚举根节点通过一次循环节可到达的节点X，以此不断复读下去直到离开T，同时我们把所有以now为根的，不包含x的子树 的染色连通块截取下来，并将它们以now为根，合并成一个染色"并"树（这里引用了官方题解的说法），很明显的是该并树包含了我们一次操作中所要包含到的所有节点。

若该树的大小为size，与X相对位移为x（其实就是深度），那么最优的构造方案即为2*(size-1)-x，即除了X及其链上的点只走一次外，其他均走2次。

由于我们枚举X是O(N)的，建个并树也是O(N)的，所以O(N^2)稳过~

当然，理论很简单，但在代码实现方面仍有些小问题。比方说这个"并"树，我们到底是如何得到的呢？

我们可以类比线段树合并的思想（反正都是二叉树），若原来没有点就新建一个，原来有点的话就直接合并，最后特判一下别搜到x的子树就行啦，详细可以看我丑陋的代码：

#include <iostream>
#include <cstring>
#define inf 2147483647
using namespace std;

struct ed{
    int ls,rs,f,sz,dd;
}p[3000],c[3000];
string s;
int st,lq,ans=inf/2;

int build(int fa,int poi)  //初始化建树 
{
    p[poi].f=fa; p[poi].sz=1; p[poi].dd=p[fa].dd+1; 
    if (s[poi]=='3') {
        p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;
        p[poi].rs=build(poi,poi+p[poi].sz), p[poi].sz+=p[p[poi].rs].sz;}
    if (s[poi]=='2') 
        p[poi].rs=build(poi,poi+1), p[poi].sz+=p[p[poi].rs].sz;
    if (s[poi]=='1')
        p[poi].ls=build(poi,poi+1), p[poi].sz+=p[p[poi].ls].sz;
    return poi;
}

int gd(int now,string t)
{   int l=t.size();
    for (int i=0;i<l;i++) now=((t[i]=='L')?p[now].ls:p[now].rs);
    return now;
}

int merge(int now,int cs,int sp)  //求并树 
{   
    if (!now) return cs;
    if (!cs) cs=++st; c[cs].sz=1;
    if (now==sp) return cs;
    c[cs].ls=merge(p[now].ls,c[cs].ls,sp); c[cs].sz+=c[c[cs].ls].sz;
    c[cs].rs=merge(p[now].rs,c[cs].rs,sp); c[cs].sz+=c[c[cs].rs].sz;
    return cs;
}

int find(string rep)
{
    int now=1,last=0;
    while (now){  //若now=0，则退出 
        last=now , now=gd(now,rep); 
        merge(last,1,now);
    }
    return c[1].sz;
}

void search(int now,string rep){  //找相对位置 
    int cnt=0;
    if (now==0) return;
    if (now!=1) {
        memset(c,0,sizeof(c)); st=1; cnt=find(rep);
        ans=min(ans,2*(cnt-1)-p[now].dd+1);
    }

    search(p[now].ls,rep+'L');
    search(p[now].rs,rep+'R');
}

int main()
{
    cin>>s; lq=s.size(); s='.'+s; 
    build(0,1);
    search(1,"");
    cout<<ans<<endl;
}

写题解比敲代码耗时长，困死了