题解 CF1464F 【My Beautiful Madness】

w4p3r · 2020-12-23 22:20:56 · 题解

（怎么连续两场1F都是树上的神仙题啊）

首先考虑能不能找到一个形式化的点，使得只要有交集就包含这个点。

发现真有这么一个点，那就是所有路径的lca深度最大的一个的d级祖先（若不存在则为根节点）。不妨假设这条路径为p，这个d级祖先为u，证明如下：

首先lca在u子树内的路径一定满足条件（否则有深度更大的lca）。

否则，若u不是某条不在u子树内的路径q的d邻居内，那么p和q之间一定没有交集（这种情况u是最有可能属于交集的）。

现在我们就把问题转换为了，某个确定的点u是否属于所有路径的d邻居（这个u肯定是十分容易找到的）。

假设u的d级祖先为v（若不存在则为根节点），那么首先要满足的是每条路径与v的子树有交集。这个问题可以用树上差分+子树求和解决。

然后，对于lca在v子树外的路径是肯定满足条件的（其一定经过v）。对于v子树内的路径，只要满足其lca与u的dis\le d即可。

那么现在的问题相当于：

1.将某点设为关键点。

2.将某点设为非关键点。

3.询问一个子树内关键点到x的最长距离。

这个问题可以用维护区间直径解决，然后这道题就愉快的解决了，时间复杂度O(nlogn)。（要是有什么不懂的可以看代码）。

代码

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register int
#define fr first
#define sd second
#define pa pair<int,int>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline int lowbit(int x){return x&(-x);}
int n,q;
vector<int>e[N];int fa[N][21],deep[N];
int L[N],R[N],Time,nowm,Q[N];
multiset<pa>S;  
struct path{int x,y;};

inline int LCA(int u,int v)
{
    if(deep[u]<deep[v])swap(u,v);
    REP(i,20,0)if(deep[fa[u][i]]>=deep[v])u=fa[u][i];
    if(u==v)return u;
    REP(i,20,0)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
inline int dis(int x,int y)
{
    if(x<0||y<0)return -inf;
    return deep[x]+deep[y]-2*deep[LCA(x,y)];
}
path operator +(path a,path b)
{
    int x=-1,y=-1,d=-inf;
    if(dis(a.x,a.y)>d)d=dis(a.x,a.y),x=a.x,y=a.y;
    if(dis(a.x,b.x)>d)d=dis(a.x,b.x),x=a.x,y=b.x;
    if(dis(a.x,b.y)>d)d=dis(a.x,b.y),x=a.x,y=b.y;
    if(dis(a.y,b.x)>d)d=dis(a.y,b.x),x=a.y,y=b.x;
    if(dis(a.y,b.y)>d)d=dis(a.y,b.y),x=a.y,y=b.y;
    if(dis(b.x,b.y)>d)d=dis(b.x,b.y),x=b.x,y=b.y;
    return (path){x,y};
}
void dfs(int x,int father)
{
    fa[x][0]=father;FOR(i,1,20)fa[x][i]=fa[fa[x][i-1]][i-1];
    deep[x]=deep[father]+1;L[x]=++Time;Q[Time]=x;
    for(int y:e[x])if(y!=father)dfs(y,x);R[x]=Time;
}
namespace S1
{
    int c[N];
    inline void add(int x,int v){for(;x<=n;x+=lowbit(x))c[x]+=v;}
    inline int qry(int x){int s=0;for(;x;x-=lowbit(x))s+=c[x];return s;}
    inline int qry(int l,int r){return qry(r)-qry(l-1);}
}
namespace S2
{
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid ((l+r)>>1)
    int sum[N];path t[N<<2];
    void build(int l,int r,int x)
    {
        t[x]=(path){-1,-1};if(l==r)return ;
        build(l,mid,ls);build(mid+1,r,rs);
    }
    void upd(int l,int r,int x,int pos,int opt)
    {
        if(l==r)
        {
            if(opt==+1){t[x]=(path){Q[l],Q[l]};}
            if(opt==-1){t[x]=(path){-1,-1};}
            return ;
        }
        if(pos<=mid)upd(l,mid,ls,pos,opt);
        else upd(mid+1,r,rs,pos,opt);
        t[x]=t[ls]+t[rs];
    }
    path qry(int l,int r,int x,int left,int right)
    {
        if(l==left&&right==r)return t[x];
        if(right<=mid)return qry(l,mid,ls,left,right);
        else if(left>mid)return qry(mid+1,r,rs,left,right);
        else return qry(l,mid,ls,left,mid)+qry(mid+1,r,rs,mid+1,right);
    }
    inline void add(int x)
    {
        if(!sum[x])upd(1,n,1,L[x],+1);
        sum[x]++;
    }
    inline void del(int x)
    {
        sum[x]--;
        if(!sum[x])upd(1,n,1,L[x],-1);
    }//一个点可以出现多次哦
}
inline int FA(int x,int d)
{
    if(deep[x]<=d)return 1;//不存在为根节点
    REP(i,20,0)if((1<<i)<=d){d-=(1<<i),x=fa[x][i];}
    return x;
}
inline int ask(int d)
{
    int v=(*(--S.end())).sd;v=FA(v,d);int t=FA(v,d);
    if(S1::qry(L[t],R[t])!=nowm)return 0;//不是所有路径与v子树有交集
    path p=S2::qry(1,n,1,L[t],R[t]);//区间最长链
    if(dis(v,p.x)<=d&&dis(v,p.y)<=d)return 1;//x到这些点的最长路径一定是最长链端点之一
    else return 0;
}
int main()
{
    //ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),q=read();
    FOR(i,1,n-1)
    {
        int x=read(),y=read();
        e[x].pb(y),e[y].pb(x);
    }
    dfs(1,0);S2::build(1,n,1);
    while(q--)
    {
        int opt=read();
        if(opt==1)
        {
            int u=read(),v=read();int z=LCA(u,v);
            S1::add(L[u],1);S1::add(L[v],1);S1::add(L[z],-1);//树上差分
            S2::add(z);nowm++;
            S.insert(mp(deep[z],z));
        }
        if(opt==2)
        {
            int u=read(),v=read();int z=LCA(u,v);
            S1::add(L[u],-1);S1::add(L[v],-1);S1::add(L[z],1);
            S2::del(z);nowm--;
            S.erase(S.lower_bound(mp(deep[z],z)));
        }
        if(opt==3)
        {
            int d=read();
            ask(d)?cout<<"Yes\n":cout<<"No\n";
        }
    }
    return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq