P8844 [Tranquility Cup #4 Preliminaries] Cass and the Fallen Leaves

Original title side:P8844 [Tranquility Cup #4 Preliminaries] Cass and the Fallen Leaves

Approximate subject matter:

Here's one for you.\(n(1\le n\le 10^5)\) A rooted tree of nodes, with the root node labeled\(1\), the depth of the root node is\(1\)The first nodes of the whole tree are green.

Cass has\(m(1\le m \le 10^5)\) An operation.

Operation 1: Color the whole tree green, after which let the depth of\(\ge x\) The knots turn yellow.

Operation 2: Ask a node\(x\) How many yellow nodes are there in the subtree of the

The first thing that can be thought of is the violent approach. Violently querying the depth of each query\(\ge x\) The number of nodes with a time of\(O(n^2)\)

Next consider how to optimize. How to ask the state of the nodes within the whole subtree? Think of the dfs order. Within a subtree, the dfs order is continuous. A subtree\(x\) (used form a nominal expression)\(dfn\) The scope is\(dfn_x\) --> \(dfn_x+siz_x-1\)

So the problem translates into, in querying a certain\(dfn\) Within the range, all depths greater than\(x\) of the number of nodes. One can think of this as a two-dimensional partial order problem. It is possible to put each point of the\(dfn\) Taking the horizontal coordinates, the\(deep\) As a vertical coordinate, all queries are processed offline and then processed in a tree array.

duration\(O(nlogn)\)

Code：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}
const int N=1e5+5;
int n,m;
vector<int>v[N];
int cnt,dfn[N],siz[N];
int dep[N],maxd;
void dfs(int x,int fa){
    dfn[x]=++cnt;
    siz[x]++;
    for(auto i:v[x]){
        if(i==fa)continue;
        dep[i]=dep[x]+1;
        maxd=max(maxd,dep[i]);
        dfs(i,x);
        siz[x]+=siz[i];
    }
}
int ans[N];
int cnt1,cnt2;
struct node{
    int x,y;
    int id,ff;
    bool operator<(const node& p)const{
        if(x==)return y<;
        else return x<;
    }
}a[N],b[N];
int c[N];
inline int lowbit(int x){
    return x&-x;
}
inline void upd(int x,int w){
    for(int i=x;i<=maxd;i+=lowbit(i)){
        c[i]+=w;
    }
}
inline int qur(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=c[i];
    }
    return res;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        v[x].emplace_back(y);
        v[y].emplace_back(x);
    }
    dep[1]=1;
    dfs(1,0);
    for(int i=1;i<=n;i++){
        a[i].x=dfn[i],a[i].y=dep[i];
    }
    sort(a+1,a+1+n);
    int now=maxd+1;
    for(int i=1;i<=m;i++){
        int op=read();
        if(op==1)now=read();
        else{
            int x=read();
            cnt2++;
            if(now>maxd){
                ans[cnt2]=0;
                continue;
            }
            else if(now==1){
                ans[cnt2]=siz[x];
                continue;
            }
            int xa=dfn[x],xb=dfn[x]+siz[x]-1,ya=now,yb=maxd;
            b[++cnt1]={xa-1,ya-1,cnt2,1};
            b[++cnt1]={xa-1,yb,cnt2,-1};
            b[++cnt1]={xb,ya-1,cnt2,-1};
            b[++cnt1]={xb,yb,cnt2,1};
        }
    }
    sort(b+1,b+1+cnt1);
    now=0;
    for(int i=1;i<=cnt1;i++){
        int x=b[i].x,y=b[i].y;
        while(now+1<=n&&a[now+1].x<=x){
            now++;
            upd(a[now].y,1);
        }
        ans[b[i].id]+=qur(y)*b[i].ff;
    }
    for(int i=1;i<=cnt2;i++)printf("%d\n",ans[i]);
    return 0;
}