CF342E Xenia and Tree解题报告

解题报告

CF342E Xenia and Tree解题报告：

更好的阅读体验

吐槽：好奇怪呀，为什么交了两份相同的代码一份AC一份WA，不应该返回相同的答案吗。

题意

• 给定一个$n$个点的树，一开始结点$1$为红点，其他点为蓝点；
• $m$次操作，操作分两类：把一个点变成红点，询问一个点离最近的红点的距离。
• 数据范围：$1\leqslant n,m\leqslant 10^5$。

分析

操作分块。

我们设定一个阈值$S$，对操作序列每$S$个操作分一块。

对于每一次询问，我们对红点分类讨论：

• 对于不在这个询问块内的红点，我们预处理出来这些红点对于询问的点的距离；
• 对于在这个询问块内的红点，我们暴力枚举然后求距离。

具体地，每跨越一次块，我们就把这个块内所有的红点bfs一遍，更新它们到所有点的距离，这是$O(n)$的，但是由于只会跨越$O(\frac{m}{S})$次块，所以总复杂度为$O(n\times\frac{m}{S})$。

对于在这个块内的红点，我们枚举它们，然后用ST表的$O(n\log n)-O(1)$的lca求距离，这样我们的复杂度为$O(S)$，总复杂度为$O(m\times S)$。

故时间复杂度为：$O(\frac{n\times m}{S}+m\times S)$，很显然$S$取$\sqrt{m}$时复杂度较优，为$O((n+m)\sqrt{m})$。

代码

分块常数小，加了个快读就到最优解了。

#include<stdio.h>
#include<math.h>
#define inf 1000000000
const int maxn=100005,maxm=200005,maxk=20,maxt=405,maxq=100005;
int n,m,e,qs,t,now;
int start[maxn],to[maxm],then[maxm],lg[maxn<<1],ST[maxn<<1][maxk],dep[maxn],in[maxn],bl[maxt],br[maxt],opt[maxq],k[maxq],dis[maxn],q[maxn];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int calc(int a,int b){
    return dep[a]<dep[b]? a:b;
}
inline void swp(int &a,int &b){
    a+=b,b=a-b,a-=b;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    dep[x]=dep[last]+1,in[x]=++qs,ST[qs][0]=x;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
        ST[++qs][0]=x;
    }
}
void getST(){
    lg[0]=-1;
    for(int i=1;i<=qs;i++)
        lg[i]=lg[i/2]+1;
    for(int i=1;i<=18;i++)
        for(int j=1;j+(1<<i)-1<=qs;j++)
            ST[j][i]=calc(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
}
int lca(int a,int b){
    if(in[a]>in[b])
        swp(a,b);
    int l=in[a],r=in[b],k=lg[r-l+1];
    return calc(ST[l][k],ST[r-(1<<k)+1][k]);
}
int getdis(int a,int b){
    int c=lca(a,b);
    return dep[a]+dep[b]-2*dep[c];
}
void bfs(int a,int b){
    qs=0;
    if(a==-1)
        q[++qs]=1;
    else for(int i=a;i<=b;i++)
        if(opt[i]==1)
            q[++qs]=k[i];
    int now=1;
    while(now<=qs){
        int x=q[now];
        now++;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(dis[y]<=dis[x]+1)
                continue;
            dis[y]=dis[x]+1,q[++qs]=y;
        }
    }
}
int query(int x,int a,int b){
    int res=dis[x];
    for(int i=a;i<=b;i++)
        if(opt[i]==1)
            res=min(res,getdis(x,k[i]));
    return res;
}
void read(int &x){
    char c=getchar();
    x=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
}
int main(){
    read(n),read(m);
    for(int i=1;i<n;i++){
        int x,y;
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs(1,0),getST();
    t=sqrt(m);
    for(int i=1;i<=t;i++)
        bl[i]=br[i-1]+1,br[i]=i*t;
    if(br[t]<m)
        t++,bl[t]=bl[t-1]+1,br[t]=m;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    int last=1;
    dis[1]=0,bfs(-1,-1);
    for(int i=1;i<=m;i++){
        if(i>br[last])
            bfs(bl[last],br[last]),last++;
        read(opt[i]),read(k[i]);
        if(opt[i]==1)
            dis[k[i]]=0;
        if(opt[i]==2)
            printf("%d\n",query(k[i],bl[last],i));
    }
    return 0;
}