P8844 [传智杯 #4 初赛] 小卡与落叶

原题面：P8844 [传智杯 #4 初赛] 小卡与落叶

大概题意：

给你一棵有 \(n(1\le n\le 10^5)\) 个结点的有根树，根结点标号为 \(1\)，根节点的深度为 \(1\)，最开始整棵树的所有结点都是绿色的。

小卡有 \(m(1\le m \le 10^5)\) 个操作。

操作一：把整棵树都染绿，之后让深度 \(\ge x\) 的结点变黄。

操作二：询问一个结点 \(x\) 的子树中有多少个黄色结点。

首先可以想到暴力做法。每次询问都暴力查询深度 \(\ge x\) 的结点的个数，时间为 \(O(n^2)\)

接下来考虑怎么优化。如何询问整个子树内的节点状态？可以想到 dfs序。在一个子树内，dfs序是连续的。一个子树 \(x\) 的 \(dfn\) 范围是 \(dfn_x\) --> \(dfn_x+siz_x-1\)

于是问题就转化成，在查询某个 \(dfn\) 范围内，所有深度大于 \(x\) 的节点数。可以想到这是一个二维偏序问题。可以将每个点的 \(dfn\) 当作横坐标，\(deep\) 当作纵坐标，将所有询问离线下来后用树状数组处理。

时间为 \(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==p.x)return y<p.y;
        else return x<p.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;
}