每日一题 dfs序专题总结

Military Problem
简单题，我们预处理出dfs序，然后查询的时候之间判断一下sz的大小，就可以了！
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 200020
int n,q,dfn[M],cnt,rev[M],sz[M]; vector<int>vec[M];
inline void dfs(int u){
    dfn[u]=++cnt,rev[cnt]=u,sz[u]=1;
    for(int i=0,TP=vec[u].size();i<TP;i++) dfs(vec[u][i]),sz[u]+=sz[vec[u][i]];
}
int main(){
    n=read(),q=read();
    for(int i=2;i<=n;i++){int x=read(); vec[x].pb(i);}
    for(int i=1;i<=n;i++) sort(vec[i].begin(),vec[i].end());
    dfs(1);
    while(q--){
        int x=read(),k=read();
        if(sz[x]<k) puts("-1"); else printf("%d\n",rev[dfn[x]+k-1]);
    }
    return 0;
}

选点
这道题是一个好题，思路非常妙，我们考虑假设我们在树上选了若干个点，然后我们按照着题目给出的大小关系去dfs，然后这个dfs序是单调增的，同时这个选出来的权值也是单调增的，这样就可以启发我们直接搞出dfs序，然后哦根据dfs序求出新的val，然后针对这个序列求一个最长上升子序列就可以了！
这个思路非常新颖，我们在类似的选点问题也可以采用一样的办法。
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 100020
int n,val[M],ls[M],rs[M],a[M],cnt,sta[M],top;
inline void dfs(int u){
    a[++cnt]=val[u];
    if(rs[u]) dfs(rs[u]); if(ls[u]) dfs(ls[u]);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<=n;i++) ls[i]=read(),rs[i]=read();
    dfs(1);
    for(int i=1;i<=n;i++){
        if(!top||a[i]>sta[top]){sta[++top]=a[i]; continue;}
        int pos=lower_bound(sta+1,sta+top+1,a[i])-sta;
        sta[pos]=a[i];
    } printf("%d\n",top);
    return 0;
}

Colorful Tree
这题要求你求生成树的大小，我们发现这个大小问题其实和https://www.luogu.com.cn/problem/P3320寻宝游戏
这道题很像只是这道题从第一个点走到最后一个点，再回来，那么容易发先每条边都被走过两遍，对于这道题我们把最后的结果除以2就可以了，
我们针对每种颜色分别维护一下，支持插入和删除，修改的时候先删除再插入即可，注意需要注意空集的特判。
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 100020
int n,tot,q,a[M],to[M<<1],nt[M<<1],fs[M];
int dep[M],fa[M][21],dfn[M],cnt,rev[M];
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;~i;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    for(int i=20;~i;i--) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
    return (x==y)?x:fa[x][0]; 
}
inline int getdis(int x,int y){return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
inline void dfs(int x,int last=0){
    dep[x]=dep[last]+1,dfn[x]=++cnt,rev[cnt]=x,fa[x][0]=last;
    for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=fs[x];i;i=nt[i]) if(to[i]^last) dfs(to[i],x);
}
#define IT set<int>::iterator
struct Sol{
    set<int>s; LL all;
    inline int fdnxt(int x){
        if(s.empty()) return -1;
        IT it=s.upper_bound(x); 
        return (it==s.end())?-1:rev[*it];
    }
    inline int fdpre(int x){
        if(s.empty()) return -1;
        IT it=s.lower_bound(x); return (it==s.begin())?-1:rev[*(--it)];
    }
    inline void Ins(int x){
        int pos=dfn[x],nx=fdnxt(pos),px=fdpre(pos);
        if((~nx)&&(~px)) all-=(LL)getdis(nx,px);
        if(~nx) all+=(LL)getdis(nx,x);
        if(~px) all+=(LL)getdis(px,x);
        s.insert(pos);
    }
    inline void Del(int x){
        int pos=dfn[x],nx=fdnxt(pos),px=fdpre(pos);
        if((~nx)&&(~px)) all+=(LL)getdis(nx,px);
        if(~nx) all-=(LL)getdis(nx,x);
        if(~px) all-=(LL)getdis(px,x);
        s.erase(pos); 
    }
    inline LL gtans(){
        if(s.empty()) return -1ll;
        return (all+getdis(rev[*s.begin()],rev[*s.rbegin()]))/2ll;
    }
    inline void debug(){
        for(IT it=s.begin();it!=s.end();it++)
            printf("%d ",*it);
        printf("\n");
    }
}P[M];

int main(){
    n=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    dfs(1); for(int i=1;i<=n;i++) a[i]=read(),P[a[i]].Ins(i);
    q=read();
    while(q--){
        char op[15]; scanf("%s",op);
        if(op[0]=='U'){
            int x=read(),y=read();
            P[a[x]].Del(x),a[x]=y,P[a[x]].Ins(x);
        } else{int x=read(); printf("%lld\n",P[x].gtans());}
        //for(int i=1;i<=3;i++) P[i].debug();
    }
    return 0;
}

Tree Requests
一道处理子树内部的问题，子树内部的处理通常我们需要用dfs序，然后如果可以离线我们可以用分治，莫队等算法在dfs序上进行，强制在线可以用一些主席树线段树分块等算法。
但是看到这道题，我写了一个和dfs序没有太大关系的dsu on the tree（之后作者应该会写一个dsu on the tree的总结）
然后我们可以用二进制优化，具体我们可以见代码
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 500020
#define pii pair<int,int>
#define mp make_pair
#define fr first
#define sc second
int n,q,tot,to[M<<1],nt[M<<1],fs[M],ans[M];
int fa[M],dep[M],sz[M],mxs[M],hv[M],typ;
char ch[M]; vector<pii >vec[M];
inline void link(int u,int v){to[++tot]=v,nt[tot]=fs[u],fs[u]=tot;}
inline void dfs(int u){
    dep[u]=dep[fa[u]]+1,sz[u]=1;
    for(int i=fs[u];i;i=nt[i]) if(to[i]^fa[u]){
        dfs(to[i]),sz[u]+=sz[to[i]];
        if(sz[to[i]]>sz[mxs[u]]) mxs[u]=to[i];
    }
}
inline void chg(int u,int Lim){
    if(typ==-1) hv[dep[u]]=0; else hv[dep[u]]^=(1<<(ch[u]-'a'));
    for(int i=fs[u];i;i=nt[i]) if((to[i]^fa[u])&&(to[i]^Lim)) chg(to[i],Lim);
}
inline bool Judge(int x){return __builtin_popcount(x)<2;}
inline void dfst(int u,int flag=0){
    for(int i=fs[u];i;i=nt[i]) if((to[i]^fa[u])&&(to[i]^mxs[u])) dfst(to[i],1);
    if(mxs[u]) dfst(mxs[u],0);
    typ=1,chg(u,mxs[u]);
    for(int i=0,TP=vec[u].size();i<TP;i++) ans[vec[u][i].sc]=Judge(hv[vec[u][i].fr]);
    if(flag) typ=-1,chg(u,0);
}
int main(){
    n=read(),q=read();
    for(int i=2;i<=n;i++) fa[i]=read(),link(fa[i],i);
    scanf("%s",ch+1),dfs(1);
    for(int i=1;i<=q;i++){
        int x=read(),y=read();
        vec[x].pb(mp(y,i));
    } dfst(1);
    for(int i=1;i<=q;i++) puts(ans[i]?"Yes":"No");
    return 0;
}

求和
一道裸题，我们直接树状数组的基本操作放到dfs序上就可以了

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 1000020
int n,m,rt,val[M],tot,to[M<<1],nt[M<<1],fs[M],L[M],R[M],cnt; LL sum[M];
inline void link(int u,int v){to[++tot]=v,nt[tot]=fs[u],fs[u]=tot;}
inline void dfs(int u,int last=0){
    L[u]=++cnt;
    for(int i=fs[u];i;i=nt[i]) if(to[i]^last) dfs(to[i],u);
    R[u]=cnt;
}
inline void mdf(int x,int y){for(int i=x;i<=n;i+=(i&-i)) sum[i]+=(LL)y;}
inline LL qry(int x,int y){
    LL ret=0;
    for(int i=y;i;i-=(i&-i)) ret+=sum[i];
    for(int i=x-1;i;i-=(i&-i)) ret-=sum[i];
    return ret;
}
int main(){
    n=read(),m=read(),rt=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<n;i++){int u=read(),v=read(); link(u,v),link(v,u);}
    dfs(rt); for(int i=1;i<=n;i++) mdf(L[i],val[i]);
    while(m--){
        int opt=read(),x=read();
        if(opt==1){int y=read(); mdf(L[x],y);}
        else printf("%lld\n",qry(L[x],R[x]));
    }
    return 0;
}

Propagating tree
其实这道题的思维难度并不高，
这道题的操作虽然感觉很麻烦，但是发现它操作的本质无非就是对于奇偶分别讨论，就这么两种情况，那么我们针对奇偶分别维护一个树状数组就可以了，和上面的题感觉本质差不多。
代码：

每日一题 dfs序专题 总结

全站热榜

创作者周榜

每日一题 dfs序专题总结