dfs序专题

Before the content

很多好题
收获颇丰

something of dfs序

概念：在对树进行深度优先遍历时,对于每个节点,在刚进入递归后以及即将回溯前记录一次该点的编号，最后产生的长度为2*N的节点序列就称为树的dfs序

void dfs(int x)
{
         a[++m]=x;
         v[x]=1;
         for (int i=h[x];~i;i=nex[i])
         {
             int j=ver[i];
             if(v[j]) continue;
             dfs(j);
         } 
         a[++m]=x;
}

特点：你可以把他理解为一个时间戳，相当于通过每一个点被遍历到的顺序将这棵树拉成了一条链。每一个节点在序列中恰好出现了两次(当然,有时只需要记录一次),设为 $图片说明$ ,那么以闭区间 $图片说明$ 就是以x为根的子树的dfs序,当然，我更多采用的是记录x子树中的节点数，那么[ $图片说明$ ]就是他子树的dfs序区间
经典用法：
1. 配合树状数组进行区间修改，单点查询
2. 用于树链剖分进行更多的操作
3. 树上莫队
4. 更多的靠做题发现(我只会这么多QwQ)

例题

Military Problem

题意：给出n-1对关系(构成一棵树),q个询问,包含 $图片说明$ ,表示一个命令从u点下达,问在他的子树中第v个收到命令的节点编号

分析：不是才学完dfs序吗？在这颗子树中，第v个收到命令的那就是dfs序为 $图片说明$ 的节点

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+1e3;

int n,q,tot,cnt;
int dfn[N],id[N],siz[N];

vector<int>g[N];

inline void dfs(int u)
{
    dfn[u]=++cnt;
    id[cnt]=u;
    siz[u]=1;

    int len=g[u].size();
    for (int i=0;i<len;i++)
    {
        int j=g[u][i];

        dfs(j);

        siz[u]+=siz[j];
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for (int i=2,x;i<=n;i++)
        scanf("%d",&x),g[x].push_back(i);

    dfs(1);

    while(q--)
    {
        int u,k;
        scanf("%d%d",&u,&k);
        if(siz[u]<k) puts("-1");
        else printf("%d\n",id[dfn[u]+k-1]);
    }

    return 0;
}

选点

分析：题目中说，如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。如果我们把这颗树拉成一条链，根据规律左节点>右节点>根节点，相当于在这个序列上求出一个最长下降子序列。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,cnt,tot;
int ch[2][N],a[N],f[N],k[N];

inline void dfs(int u)
{
    if(!u) return ;
    a[++tot]=k[u];
    dfs(ch[1][u]);
    dfs(ch[0][u]);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&k[i]);
    for (int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ch[0][i]=x,ch[1][i]=y;
    }

    dfs(1);

    f[++cnt]=a[1];
    for (int i=2;i<=n;i++)
    {
        if(a[i]>f[cnt]) f[++cnt]=a[i];
        else
        {
            int pos=lower_bound(f+1,f+cnt+1,a[i])-f;
            f[pos]=a[i];
        }
    }

    printf("%d\n",cnt);

    return 0;
}

Tree Requests

题意：给出一棵树，树上的每一个节点都有一个对应的字符。定义一个节点的深度为节点到根节点1的路径上点的数量。有m个询问，每次包含一个 $图片说明$ ,问在子树u中深度为v的节点上的字符经过重新排列能否形成一个回文串

分析：我发现他结合了两道题，大家有兴趣可以去看看:小睿睿的兄弟 & Hyperdrome同时附上我的题解题1&题2。然后让我们步入正题，判断他能否构成一个回文串，我只需要状态压缩每一个字母的个数，然后通过dfs序，通过二分求出在第v层中属于子树u的节点(题二解法)，再通过前缀和，判断是否合法(题一解法)。这种结合，也许就是算法的美妙。避免了麻烦的树剖。

#include<bits/stdc++.h>

#define inf 1e9

using namespace std;

const int N=5e5+10;

int n,tot,m,cnt,dt;
int h[N],nex[N],ver[N];
int id[N],dfn[N],siz[N],dep[N],a[N];

char k[N];

vector<int>g[N],f[N];

inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    dep[u]=dep[v]+1;dt=max(dt,dep[u]);
    dfn[u]=++cnt,id[cnt]=u;siz[u]=1;
    g[dep[u]].push_back(cnt);
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        siz[u]+=siz[j];
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for (int i=2,x;i<=n;i++)
        scanf("%d",&x),add(x,i);

    dfs(1,0);

    scanf("%s",k);
    for (int i=1;i<=n;i++) a[i]=k[i-1]-'a';
    for (int i=1;i<=dt;i++)
    {
        int len=g[i].size();
        int now=0;
        f[i].push_back(0);
        for (int j=0;j<len;j++)
        {
            now^=(1<<(a[id[g[i][j]]]));
            f[i].push_back(now);
        }//dfs序肯定是连续的
        g[i].push_back(inf);
    }

    int x,y,xx,yy,l,r;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        //输入子树和深度
        if(y>dt)
        {
            puts("Yes");
            continue;
        }
        l=0,r=g[y].size()-1,xx=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(g[y][mid]<dfn[x]) l=mid+1;
            else r=mid-1,xx=mid;
        }
        l=0,r=g[y].size()-1,yy=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(g[y][mid]<=dfn[x]+siz[x]-1) l=mid+1;
            else r=mid-1,yy=mid;
        }//二分求出在第y层中属于子树u的节点的dfs序范围

        if(xx<0||yy<0)
        {
            puts("Yes");
            continue;
        }//不存在 

        int ans=(f[y][yy]^f[y][xx]);

        int up=0;
        while(ans) up++,ans-=(ans&(-ans));

        if(up<=1) puts("Yes");
        else puts("No");
    }

    return 0;
}

求和

分析：先引用一下上面那一张图

可以确定，每一刻子树中的dfs序是连续的。那么我们就在dfs序上建立一棵线段树，对于操作一，单点修改，对于操作二，区间查询 $图片说明$

#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

#define ls now<<1
#define rs now<<1|1

using namespace std;

const int N=1e6+10;

int n,m,k,tot,cnt;
int h[N],nex[N<<1],ver[N<<1];
int val[N],dfn[N],id[N],siz[N],w[N],s[N<<2];

inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    dfn[u]=++cnt;id[cnt]=u;
    w[cnt]=val[u];siz[u]=1;

    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        siz[u]+=siz[j];
    }
}

inline void build(int now,int l,int r)
{
    if(l==r)
    {
        s[now]=w[l];
        return ;
    }

    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);

    s[now]=s[ls]+s[rs];
}

inline void add(int now,int l,int r,int x,int v)
{
    s[now]+=v;
    if(l==r) return ;

    int mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,v);
    else add(rs,mid+1,r,x,v);
}

inline int find(int now,int l,int r,int x,int y)
{
    if(l>=x&&r<=y) return s[now];

    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret+=find(ls,l,mid,x,y);
    if(mid<y) ret+=find(rs,mid+1,r,x,y);

    return ret;
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

    dfs(k,0);build(1,1,n);

    int opt,x,v;
    while(m--)
    {
        scanf("%d%d",&opt,&x);
        if(opt==2)
            printf("%d\n",find(1,1,n,dfn[x],dfn[x]+siz[x]-1));
        else
        {
            scanf("%d",&v);
            add(1,1,n,dfn[x],v);
        }
    }

    return 0;
}

Propagating tree

题意：给定一棵n个节点的树，它的根是1号节点。这棵树每个点都有一个权值，你需要完成这两种操作：
1. u val 表示给u节点的权值增加val
2. u 表示查询u节点的权值
它还有个神奇的性质：当某个节点的权值增加val时，它的子节点权值都增加-val，它子节点的子节点增加-(-val)...... 如此一直进行到树的底部。

分析：可以发现,奇数层会增加的权值相同,偶数层增加的权值相同,那用两个树状数组维护一下奇数层与偶数层。但是想一想,能否通过一个树状数组维护这个结果。因为对权值的加减只与节点的深度有关。先不考虑符号，通过差分就能实现区间修改,单点查询。
把深度加入考虑
1.如果当前的u节点的深度是奇数,那么其下的所有子节点，奇数层+相同权值,偶数层-相同权值
2.如果当前的u节点的深度是偶数,那么其下的所有子节点，奇数层-相同权值,偶数层+相同权值
但是他们的初值是不变的，只需要决定修改的值的正负就好

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

const int N=2e5+10;

int n,m,tot,idx;
bool vis[N];
int st[N],k[N],dep[N],ed[N];
int h[N],nex[N<<1],ver[N<<1],val[N];

inline void add(int x,int y)
{
    nex[idx]=h[x];
    ver[idx]=y;
    h[x]=idx++;
}

inline void dfs(int u,int pre)
{
    st[u]=++tot;
    dep[u]=dep[pre]+1;vis[u]=1;

    for (int i=h[u];~i;i=nex[i])
        if(!vis[ver[i]])
            dfs(ver[i],u);

    ed[u]=tot;
}

inline int lowbit(int x)
{
    return x&(-x);
}

inline void akd(int x,int y)
{
    while(x<=tot)
    {
        k[x]+=y;
        x+=lowbit(x);
    }
}

inline int find(int x)
{
    int res=0;
    while(x)
    {
        res+=k[x];
        x-=lowbit(x);
    }

    return res;
}

int main()
{
    memset(h,-1,sizeof(h));

    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&val[i]);

    int x,y,z;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

    dfs(1,0);

    int ans=0;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        if(x==1)
        {
            scanf("%d",&z);
            if(dep[y]&1) akd(st[y],z),akd(ed[y]+1,-z);
            else akd(st[y],-z),akd(ed[y]+1,z);
        }
        else
        {
            ans=find(st[y]);
            if(dep[y]&1) ans=val[y]+ans;
            else ans=val[y]-ans;

            printf("%d\n",ans);
        }
    }

    return 0;
}

每日一题文章被收录于专栏

每天的题，为了牛币