题解：P12205 [COI 2022] 通行证件 / Vinjete

· · 题解

给定一棵 n 个节点的树，第 i 条边可表示为四元组 \{u_i,v_i,l_i,r_i\}，其含义为这条边连接节点 u,v，并且有两个额外属性 l,r。对于每个 i 求 |\{x|\exists\ e \in \text{path}(1,i) : l_e \leq x \leq r_e\}|，其中 \text{path}(u,v) 表示 u 到 v 路径上所有边构成的集合。

由于要求出每个点到根链的信息，考虑 dfs 遍历整棵树，并使用某种数据结构实时维护到根链信息，在加入一条边时，往数据结构中加入 (l,r)，回溯时撤销操作。

我们每次撤销的都是上一次加入操作，因此撤销复杂度永远不会超过加入复杂度，因此我们只需要考虑区间的加入，然后再回溯的时候暴力撤销。

我们需要维护一个数据结构，支持每次往集合中加入一个区间并求出当前集合中区间并集的大小。这可以转化为每次将一个区间全部改为 1 然后全局求和，显然线段树支持这个功能。

至此，本题完结，时空复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
    int v,l,r;
};
vector<edge> V[100005];
int b[200015],tot;
int getid(int x){
    return lower_bound(b+1,b+1+tot,x)-b;
}
struct node{
    int l,r;
    int len,sum;
    int tag;
}t[800015];
void build(int p,int l,int r){
    t[p].len=b[r+1]-b[l];
    t[p].l=l,t[p].r=r;
    if(l==r) return;
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
}
struct stk{
    int p,id;
    node val;
};
stack<stk> S;
void pushup(int p,int id){
    S.push({p,id,t[p]});
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void fil(int p,int id){
    S.push({p,id,t[p]});
    t[p].sum=t[p].len;
    t[p].tag=1;
}
void pushdown(int p,int id){
    S.push({p,id,t[p]});
    if(t[p].tag){
        t[p].tag=0;
        fil(p*2,id);
        fil(p*2+1,id);
    }
}
void modify(int p,int l,int r,int id){
    if(t[p].sum==t[p].len) return;
    if(l<=t[p].l&&t[p].r<=r){
        fil(p,id);
        return;
    }
    pushdown(p,id);
    int mid=(t[p].l+t[p].r)/2;
    if(mid>=l) modify(p*2,l,r,id);
    if(mid<r) modify(p*2+1,l,r,id);
    pushup(p,id); 
}
int ans[100005];
void dfs(int u,int fa){
    ans[u]=t[1].sum;
    for(auto nx:V[u]){
        int v=nx.v,l=nx.l,r=nx.r;
        if(v==fa) continue;
        modify(1,getid(l),getid(r+1)-1,v);
        dfs(v,u);
        while(!S.empty()&&S.top().id==v){
            int p=S.top().p;
            t[p]=S.top().val; 
            S.pop();
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        V[u].push_back({v,l,r});
        V[v].push_back({u,l,r});
        b[++tot]=l,b[++tot]=r+1; 
    }
    b[++tot]=1,b[++tot]=m+1;
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    build(1,1,tot-1);
    dfs(1,0);
    for(int i=2;i<=n;i++) cout<<ans[i]<<"\n"; 
    return 0; 
}