牛半仙的妹子Tree题解

P7GAB · 2024-11-19 08:16:28 · 题解

题面

做法

先补一下ST表求LCA的做法。

欧拉序就是dfs遍历这颗树经过每个节点的顺序。

欧拉序有一个优美的性质，就是给定两个端点 l,r ，则 [l,r] 之间深度最小值即是 l,r 的LCA。

我们 dfs 时需要统计 dep_u,dfn_u 以及欧拉序

如图，其欧拉序为1 5 6 5 1 2 4 2 3 2 1

比如6与4之间的最小值为1，显然该点就是这两点的LCA。

由于一个有儿子的点可能被经过不止一次，所以序列长度比 n 大很正常。

我们还需要一个dfn数组来统计每个节点第一次被经过的时间，当然这个时间戳依然可能比 n 大,所代表的就是其第一次在欧拉序中出现的位置。

对于上图，其dfn为1 6 9 7 2 3，两者的联系就在于dfn_i 代表的是对于节点 i 第一次出现在欧拉数组中的下标是 dfn_i 。

比如 dfn_2 为6，而其在欧拉序中首次出现的位置也是6。

欧拉序找LCA就是对于一个欧拉序数组，一组查询为 u,v，我们应当在 [dfn_u,dfn_v] 间找深度最小值，ST表显然可以维护。

在建表时，由于欧拉序的性质，应当选择深度较小的，而不是简单的取min(st[i][j-1],st[i+(1<<(j-1))][j-1])。

在询问时，对于两个点 u,v ，先利用 dfn_u,dfn_v 找到在欧拉序中第一次出现的位置，然后再取深度较小点作为LCA。

再回到题目，不妨朴素的想，考虑每个点是否被染色，就要遍历上一次清零后的所有染色操作，设染色操作染了 x，询问点是 y，dis_{x,y} 表示两点距离, TIME_i 表示对于 i 点操作的时间，如果 dis_{x,y} \le TIME_{y}-TIME_{x} 那显然已经扩展到了。

考虑分块，由于操作是按时间顺序排序的，我们对于操作分块。

我们设块长为 len ，对于每个块内的染色操作，我们直接暴力判断，即在一个块内从上一次清零时刻+1开始(可能本块没有，直接从左端点开始)。

还有一种情况，就是上一次清零在块外面（上面的情况已经保证统计到被块内染色的情况），如果我们能够知道该点是否被块外的染色操作染色，即可 O(1) 判断。

假设该块之前的都已经算完了，我们现在枚举染色时间，判断该块中的染色操作是否会更新要染的这个点的染色时间，因为如果当前染色操作的时间比该点被染色的时间还要晚，那显然不用更新，如果可以，将当前块的所有染色操作加入队列并更新被染点的时间。进行Bfs，如果染色操作会使某个点最早被染色时间更早就修改，否则不修改，枚举完时间后将队列中剩下的点继续扩展直到遍历整棵树。

这样复杂度是 O(n) 的。

块长为 len 块数为 m/len ,时间复杂度为 O(m/len \times (n + len^2))，len 取 \sqrt{n}，n,m 同阶即为 O(m \times \sqrt{n})。

code

#include<bits/stdc++.h>
using namespace std;
#define syt cerr<<"sytakioi"<<endl;
const int maxn=2e5+10,inf=0x3f3f3f3f;
struct node {
    int nxt,to;
} edge[maxn<<1];
struct OP {
    int op,x;
} op[maxn<<1];
int head[maxn<<1],cnt=0;
void add(int u,int v) {
    cnt++;
    edge[cnt].to=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int st[maxn<<1][30],fa[maxn<<1];
int tim[maxn],l[maxn],r[maxn];
int n,m,num=0;
int dep[maxn<<1],rl[maxn<<1],dfn[maxn<<1];
void dfs(int u,int fath) {
    rl[++num]=u;
    dep[u]=dep[fath]+1;
    dfn[u]=num;
    fa[u]=fath;
    for(int i=head[u]; i; i=edge[i].nxt) {
        int v=edge[i].to;
        if(v==fath) continue ;
        dfs(v,u);
        rl[++num]=u;
    }
}
int lca(int x,int y) {
    int u=dfn[x],v=dfn[y];
    if(u>v)
        swap(u,v);
    int len=log2(v-u+1);
    int uu=st[u][len],vv=st[v-(1<<len)+1][len];
    if(dep[uu]<dep[vv])
        return uu;
    else
        return vv;
}
int dis(int u,int v) {
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int s;
int main() {
    cin>>n>>m;
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs(1,0);
//  for(int i=1; i<=n; i++)
//      cout<<dfn[i]<<" ";
//  cout<<endl;
//  for(int i=1; i<=num; i++)
//      cout<<rl[i]<<" ";
    memset(tim,inf,sizeof(tim));
    for(int i=1; i<=num; i++)
        st[i][0]=rl[i];
    for(int j=1; j<=log2(num); j++) {
        for(int i=1; i+(1<<j)-1<=num; i++) {
            int u=st[i][j-1],v=st[i+(1<<(j-1))][j-1];
            if(dep[u]<dep[v])
                st[i][j]=u;
            else
                st[i][j]=v;
        }
    }
    for(int i=1; i<=m; i++) {
        cin>>op[i].op>>op[i].x;
    }
    int len=sqrt(n);
    int blocks=m/len;
    if(blocks*len<m)blocks++;
    for(int i=1; i<=blocks; i++) {
        l[i]=len*(i-1)+1,r[i]=len*i;
    }
    r[blocks]=m;
    int gc=0;
    queue<int> q;
    //for(int i=1; i<=blocks; i++)
    //  cout<<" bl: "<<l[i]<<" "<<r[i]<<endl;
    for(int i=1; i<=blocks; i++) {
        //syt
//      for (int j = 1; j <= n; j++) {
//          cout<<tim[j]<<" ";
//      }
//      cout<<endl;
        for(int j=l[i]; j<=r[i]; j++) {
            //syt
            if(op[j].op==1) continue;
            else if(op[j].op==2) gc=j;
            else {
                bool flag=0;
                for(int k=max(gc+1,l[i]); k<=j-1; k++)

                    if(op[k].op==1 && j-k>=dis(op[k].x,op[j].x)) {
                        flag=1;
                        break;
                    }
                //cout<<flag;
                if(gc<l[i] && tim[op[j].x]<=j) flag=1;
                //syt
                if(flag==1) {
                    cout<<"wrxcsd"<<endl;

                } else
                    cout<<"orzFsYo"<<endl;

            }
        }
        while(!q.empty())
            q.pop();
        if(gc>=l[i])
            for(int j=1; j<=n; j++)
                tim[j]=inf;
        for(int j=max(gc+1,l[i]); j<=r[i]; j++) {
            if(op[j].op==1 && j<tim[op[j].x])
                tim[op[j].x]=j,q.push(op[j].x);
            while(!q.empty()) {
                int u=q.front();
                if(tim[u]>j)break;
                q.pop();
                for(int I=head[u]; I; I=edge[I].nxt) {
                    int v=edge[I].to;
                    if(tim[v]>tim[u]+1) {
                        tim[v]=tim[u]+1;
                        q.push(v);
                    }
                }
                if(tim[fa[u]]>tim[u]+1 && fa[u]) {
                    tim[fa[u]]=tim[u]+1;
                    q.push(fa[u]);
                }
            }
        }
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            for(int I=head[u]; I; I=edge[I].nxt) {
                int v=edge[I].to;
                if(tim[v]>tim[u]+1) {
                    tim[v]=tim[u]+1;
                    q.push(v);
                }
            }
            if(tim[fa[u]]>tim[u]+1 && fa[u]) {
                tim[fa[u]]=tim[u]+1;
                q.push(fa[u]);
            }
        }
    }
    return 0;
}
//
/*
6 5
1 2
2 3
2 5
1 4
4 6
*/