树的序列化

树的序列化

可以把树上的问题转化为序列，就可以数据结构了（还有 DS 大神）。

DFS 序

即按 DFS 的顺序。
特性：

• 子树在 DFS 序中是连续的
• 子树的区间是包含该子树的子树区间（判断是否是祖先）

可用来进行子树操作。

void dfs(int u,int pre){
    lpos[u]=++tot;//即常见的 dfn
    id[tot]=u;
    sz[u]=1;
    for(auto v:g[u])
        if(v!=pre) dfs(v,u),sz[u]+=sz[v];
    rpos[u]=tot;//即 dfn+sz
}

例题

CF877E

dfn 上线段树

#include<bits/stdc++.h>
#define ls o<<1
#define rs o<<1|1
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,a[N],dfn[N],id[N],sz[N],tot;
vector<int> g[N];
void dfs(int u,int pre){
    dfn[u]=++tot,sz[u]=1;
    id[tot]=u;
    for(int v:g[u])
        if(v!=pre) dfs(v,u),sz[u]+=sz[v];
}
/*省略区间覆盖线段树*/
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int p;
    for(int i=2;i<=n;i++) cin>>p,g[p].push_back(i);
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1,0);
    build(1,1,tot);
    int q;
    cin>>q;
    string op;
    int x;
    while(q--){
        cin>>op>>x;
        if(op=="get"){
            cout<<query(1,1,tot,dfn[x],dfn[x]+sz[x]-1)<<'\n';
        }
        else update(1,1,tot,dfn[x],dfn[x]+sz[x]-1);
    }
    return 0;
}
/*g++ -O2 -std=c++17 test.cpp -o test && .\test< in.txt > out.txt*/

ABC294G

记 $dis$ 为到根的距离，$u$ 和 $v$ 的距离为 $dis_u+dis_v-2dis_{lca(u,v)}$
更新边权只对子树的 $dis$ 有影响，在 dfn 上区间修改即可。（脑抽写了个完整区间加区间查询的线段树，导致 120 行）

#include<bits/stdc++.h>
#define ls o<<1
#define rs o<<1|1
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,a[N],dfn[N],id[N],sz[N],tot;
int dep[N],fa[N][30];
ll dis[N];
vector<pair<int,int>> g[N];
void dfs(int u,int pre){
    dfn[u]=++tot,sz[u]=1;
    id[tot]=u;
    fa[u][0]=pre;dep[u]=dep[pre]+1;
    for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; 
    for(auto [v,w]:g[u]){
        if(v==pre) continue;
        dis[v]=dis[u]+w;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
//LCA部分
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
/*省略区间加线段树*/
struct edge{
    int u,v;
    ll w;
}e[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) g[i].clear();
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        e[i]={u,v,w};
    }
    tot=0,dfs(1,0);
    build(1,1,tot);
    int q,op,x,y;
    cin>>q;
    while(q--){
        cin>>op>>x>>y;
        if(op==1){
            auto [u,v,w]=e[x];
            if(dep[u]<dep[v]) swap(u,v);
            update(1,1,tot,dfn[u],dfn[u]+sz[u]-1,y-w);//打在子节点的子树上
            e[x].w=y;
        }
        else{
            int d=lca(x,y);
            cout<<query(1,1,tot,dfn[x],dfn[x])+query(1,1,tot,dfn[y],dfn[y])-2*query(1,1,tot,dfn[d],dfn[d])<<'\n';
        }
    }
    
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}
/*g++ -O2 -std=c++17 test.cpp -o test && .\test< in.txt > out.txt*/

CF1328E

注意到点要么在这条链上，要么父亲在这条链上。
对于前者，除了根节点其父亲也在链上，我们直接看所有节点的父亲是不是在同一条链上就好了。
我选择按深度排序，然后用 dfn 判断后面的是不是前面子树区间中的。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,Q,fa[N],dfn[N],id[N],sz[N],tot,dep[N];
vector<int> g[N];
void dfs(int u,int pre){
    fa[u]=pre,dep[u]=dep[pre]+1;
    dfn[u]=++tot,sz[u]=1;
    id[tot]=u;
    for(int v:g[u]){
        if(v==pre) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>Q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    int k,a[N];
    while(Q--){
        cin>>k;
        for(int i=1;i<=k;i++) cin>>a[i],a[i]=(a[i]==1?1:fa[a[i]]);
        sort(a+1,a+k+1,[](int x,int y){return dep[x]<dep[y];});
        bool ok=1;
        for(int i=2;i<=k;i++){
            if(dfn[a[i]]<dfn[a[i-1]]||dfn[a[i]]>=dfn[a[i-1]]+sz[a[i-1]]){
                ok=0;
                break;
            }
        }
        if(ok) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
/*g++ -O2 -std=c++17 test.cpp -o test && .\test< in.txt > out.txt*/