CF1464F My Beautiful Madness 题解

zyxawa · 2022-08-30 21:46:00 · 题解

CF1464F My Beautiful Madness

Meaning

定义树上一条路径的 d 邻居（一个点集）S：x \in S 当前仅当存在一个路径上的点 y 满足 dis_{x,y}\le d，有三个操作：加边，删边，询问所有路径的 d 邻居交集是否为空（通俗一点就是：是否存在一个点使它到所有路径距离（到路径上点的距离的最小值）比 d 小）。

Solution

我们难以判断路径关系，欲求一种简单的等价的容易判断的表示法，可以抓住树上某一个关键点，如果有解，那它必然处于所有路径的交集，而这个关键节点则是树上最深的 LCA 的 d 级祖先，这个很好理解，~~画图感性理解一下~~。

假设我们加了 (1,3),(1,5),(7,9),(9,9) 四条边，现在询问 2，那么我们的关键节点就是 5，所有路径也都会有交，如果我们继续向上，就更不可能可能性就会更大（如果这个示例树更大一些，边数多一些，那就只有这一种情况）。

求出了关键节点后，我们又应该如何判断呢，我们可以子树内外分别考虑，对于子树内的路径满足，因为最深的 LCA 都能到达；考虑子树外的路径，因为我们选取的关键节点，即是在满足子树内的限制尽量往外走的点，所以等效代替，现在的判定变为了计算关键节点与关键节点子树外的 LCA 的距离的最小值与 2d 的关系。

同时我们令关键节点为 u，它的 d 级祖先为 v，同样的子树内外分别考虑，首先必须满足所有的路径都要经过 v 的子树（本来是和 u 有交），这个也好理解，~~脑洞画图理解一波~~。

再次假设我们加了 (7,9),(2,3),(5,7),(2,5),(9,9) 五条边，询问的是 1，可以很好的发现如果不满足的话，那它是无解的，是肯定大于 d 的，那么对于 v 子树内的路径，变成了求解 u 和 v 子树内的 LCA 最远距离，到现在那这道题就可以 AC 了（黑题呀）。

Hint

经过上面的讲解，我们可以来理一理我们需要求解的东西和需要用到的算法了：

处理出树的 dfn 序，然后倍增求 LCA。
用 multiset 记录路径和深度，每次取深度最大值。
树状数组维护树上差分，统计路径条数。
线段树维护树的直径。
判断所有路径是否经过 v 的子树，以及计算子树直径与 2d 的关系。

下面就是代码了

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,dfn,inf=0x3f3f3f3f,dep[200001],st[200001][21],ls[200001],rs[200001],cnt[200001];
vector <int> G[200001];
multiset <pair<int,int> > s;//记录路径及其lca的深度
struct spot{
    int x,y,val;
};
void get(int rt,int fa){
    ls[rt]=++dfn;
    dep[rt]=dep[fa]+1;
    st[rt][0]=fa;
    for(int i=1;i<=20;i++) st[rt][i]=st[st[rt][i-1]][i-1];
    for(int i=0;i<G[rt].size();i++){
        int to=G[rt][i];
        if(fa!=to) get(to,rt);
    }
    rs[rt]=dfn;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--){
        if(dep[st[u][i]]>=dep[v]) u=st[u][i];
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(st[u][i]!=st[v][i]){
            u=st[u][i];
            v=st[v][i];
        }
    }
    return st[u][0];
}
int dist(int u,int v){
    if(u==-1||v==-1) return -inf;
    int fa=lca(u,v);
    return dep[u]+dep[v]-2*dep[fa];
}
int find(int x,int k){
    for(int i=20;i>=0;i--){
        if((1<<i)<=k&&st[x][i]){
            k-=(1<<i);
            x=st[x][i];
        }
        else if((1<<i)<=k&&!st[x][i]) return 1;
    }
    return x;
}
spot merge(spot p,spot q){
    if(p.x==-1) return q;
    if(q.x==-1) return p;
    spot res=q;
    if(p.val>q.val) res=p;
    int a=dist(p.x,q.x),b=dist(p.x,q.y),c=dist(p.y,q.x),d=dist(p.y,q.y);
    if(res.val<a) res=spot{p.x,q.x,a};
    if(res.val<b) res=spot{p.x,q.y,b};
    if(res.val<c) res=spot{p.y,q.x,c};
    if(res.val<d) res=spot{p.y,q.y,d};
    return res;
}
struct SegmentTree{
    spot node[800001];
    void build(int rt,int l,int r){
        node[rt]=spot{-1,-1,-inf};
        if(l==r) return;
        int mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
    }
    spot query(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R) return node[rt];
        int mid=(l+r)/2;
        if(R<=mid) return query(rt*2,l,mid,L,R);
        if(L>=mid+1) return query(rt*2+1,mid+1,r,L,R);
        return merge(query(rt*2,l,mid,L,R),query(rt*2+1,mid+1,r,L,R));
    }
    void updata(int rt,int l,int r,int id,int x,int pos){
        if(l==r&&l==id){
            if(pos==1) node[rt]=spot{x,x,0};
            else node[rt]=spot{-1,-1,-inf};
            return;
        }
        int mid=(l+r)/2;
        if(id<=mid) updata(rt*2,l,mid,id,x,pos);
        else updata(rt*2+1,mid+1,r,id,x,pos);
        node[rt]=merge(node[rt*2],node[rt*2+1]); 
    }
}t1;//维护树的直径
struct TreeArray{
    int tree[800001];
    void add(int x,int n,int y){
        for(int i=x;i<=n;i+=i&-i) tree[i]+=y;
    }
    int ask(int x){
        int res=0;
        for(int i=x;i>=1;i-=i&-i) res+=tree[i];
        return res;
    }
}t2;//维护树上差分，记录路径条数
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    get(1,0);
    t1.build(1,1,n);
    while(m--){
        int pos;
        scanf("%d",&pos);
        if(pos==1){
            int x,y;
            scanf("%d%d",&x,&y);
            int z=lca(x,y);
            t2.add(ls[x],n,1);
            t2.add(ls[y],n,1);
            t2.add(ls[z],n,-1);
            s.insert(make_pair(-dep[z],z));
            cnt[z]++;
            if(cnt[z]==1) t1.updata(1,1,n,ls[z],z,1);
        }
        else if(pos==2){
            int x,y;
            scanf("%d%d",&x,&y);
            int z=lca(x,y);
            t2.add(ls[x],n,-1);
            t2.add(ls[y],n,-1);
            t2.add(ls[z],n,1);
            s.erase(s.lower_bound(make_pair(-dep[z],z)));
            cnt[z]--;
            if(cnt[z]==0) t1.updata(1,1,n,ls[z],z,0);
        }
        else{//所有路径一定要么穿过它，要么在它的子树内
            int d;
            scanf("%d",&d);
            int x=find((*s.begin()).second,d),y=find(x,d);
            if(t2.ask(rs[y])-t2.ask(ls[y]-1)!=s.size()){//不是所有路径与它的子树有交集
                printf("No\n");
                continue;
            }
            spot res=t1.query(1,1,n,ls[y],rs[y]);//区间最长链(子树直径)
            if(dist(res.x,x)<=d&&dist(res.y,x)<=d) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}