奇怪的思想——Euler Tour

引子

颓废的时候想到了这个思想，好像比较有趣。

Euler Tour

何为Euler Tour？

这是一种树的展开方式。和普通的dfs序不同的是，每个节点都会出现几次，也就是递归开始的时候和结束的时候都会记下。就是每次递归到这个点都记下。空间复杂度不佳。

这也是非常好想的，实现也很简单。

void dfs(int now,int pre)
{
    dfs_list[++dfs_clock]=now;
    for (int i=st[now];i;i=e[i].next)
        if (e[i].to!=pre)
        {
            dfs(e[i].to,now);
            dfs_list[++dfs_clock]=now;
        }
}

这个的应用有什么呢？LCA！

对于每个点记录它在Euler Tour上第一次出现的位置$first[i]$。对于Euler Tour上每个点记录一下它的深度$depth[i]$。

然后查询两点的lca就是$first[i]-first[j]$之间的$depth$最小值对应的点就是两点的lca。

这个可以用rmq实现$O(1)$。。

（好像太基础了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define M 500000*2+10
#define N 500000*2+10
using namespace std;

struct node
{
    int to,next;
}e[M];
int tot,st[M];
int n,m,root,x,y;
int f[N][20];
int dfs_list[N],depth[N],first[N];

void add(int x,int y)
{
    e[++tot].to=y;
    e[tot].next=st[x];
    st[x]=tot;
}

int pow_2(int j)
{
    return (1<<j);
}

void rmq_init()
{
    for (int i=1;i<=2*n-1;i++)
        f[i][0]=i;
    int i=1,j=1;
    for (int j=1;pow_2(j)<=2*n-1;j++)
        for (int i=1;i+pow_2(j)<=2*n-1;i++)
            if (depth[f[i][j-1]]<depth[f[i+pow_2(j-1)][j-1]])
                f[i][j]=f[i][j-1];
            else
                f[i][j]=f[i+pow_2((j-1))][j-1];
}
int rmq_query(int l,int r)
{
    int pos;
    for (pos=0;pow_2(pos)<(r-l+1);pos++);
    pos--;
    int a=depth[f[l][pos]];
    int b=depth[f[r-pow_2(pos)+1][pos]];
    if (a<b)
        return dfs_list[f[l][pos]];
    else
        return dfs_list[f[r-(1<<pos)+1][pos]];
}

int dfs_clock=0;
void dfs(int now,int pre,int deep)
{
    dfs_list[++dfs_clock]=now;
    depth[dfs_clock]=deep;
    if (!first[now])
        first[now]=dfs_clock;
    for (int i=st[now];i;i=e[i].next)
        if (e[i].to!=pre)
        {
            dfs(e[i].to,now,deep+1);
            dfs_list[++dfs_clock]=now;
            depth[dfs_clock]=deep;
        }
}

int lca(int x,int y)
{
    if (first[x]>first[y]) swap(x,y);
        //printf("%d %d\n",first[x],first[y]);
    return rmq_query(first[x],first[y]);
}

main()
{
    scanf("%d%d%d",&n,&m,&root);
    for (int i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(root,-1,0);
    rmq_init();
    for (int i=1;i<=dfs_clock;i++)
        printf("%d ",dfs_list[i]);
}
//n年前的代码，勿吐槽

下面是重头戏。

我们找一棵大点的树。