LG-T216911

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

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

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

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

思路

社团免试题。

学长开始时提示这题可以离线处理做。

但是想了好久还是没啥思路，不太懂操作一该如何处理，觉得将所有深度为 $x$ 的点的子树全都变黄这个操作十分暴力。

于是又问了问学长，学长提供了思路，明白了。

首先可以用 dfs序+线段树来维护树上点的状态，将绿色标为 $0$ ，将黄色标为 $1$ 。

然后显然地，可以根据操作一来对操作序列分段，接着根据操作一的深度从大到小来排序，因为深度小的操作会覆盖深度大的操作。

于是直接线段树维护区间和即可。

这样离线处理，每个点只操作一次，因此保证了总复杂度为 $O(n\log n)$ 。

代码

好久没写这么长的代码了（

#include<bits/stdc++.h>
#define N 100010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m,js=0,pos=0,ans[N];

int head[N],tot=0;
struct graph{
    int v,next;
}edge[N<<1];
void add_edge(int u,int v) {
    edge[++tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot; 
}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}

int cnt=0,dfn[N<<1],L[N],R[N];
vector<int> d[N];
void dfs(int u,int fa,int depth) {
    d[depth].push_back(u);
    dfn[++cnt]=u;
    L[u]=cnt;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa) continue;
        dfs(v,u,depth+1);
    }
    dfn[++cnt]=u;
    R[u]=cnt;
}

class SegmentTree{
  private:
    int sum[N<<3];
    bool lazy[N<<3];
    #define s(x) sum[x]
    #define l(x) lazy[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
    void spread(int p,int l,int r) {
        if(!l(p)) return ;
        s(ls)=mid-l+1,l(ls)=true;
        s(rs)=r-mid,l(rs)=true;
        l(p)=false;
    }
  public:
    void build(int p,int l,int r) {
        s(p)=0,l(p)=false;
        if(l==r) return ;
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            s(p)=r-l+1;
            l(p)=true;
            return ;
        }
        spread(p,l,r);
        modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);
        update(p);
    }
    int ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        spread(p,l,r);
        return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
    }
}SMT;

struct query{
    int depth;
    vector<pair<int,int> > p;
    bool operator < (const query &x) const {
        return depth>x.depth;
    }
}q[N];

int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        int u=read(),v=read();
        add(u,v);
    }

    dfs(1,1,1);
    SMT.build(1,1,cnt);
    int lst=n+1,lop=1;
    for(int i=1;i<=m;i++) {
        int op=read(),x=read();
        if(op==1) lst=x;
        else {
            if(lop==1) q[++js].depth=lst;
            q[js].p.push_back(make_pair(++pos,x));
        }
        lop=op;
    }
    sort(q+1,q+js+1);
    for(int i=1;i<=js;i++) {
        int depth=q[i].depth;
        for(int j=0;j<d[depth].size();j++) SMT.modify(1,1,cnt,L[d[depth][j]],R[d[depth][j]]);
        for(int j=0;j<q[i].p.size();j++) ans[q[i].p[j].first]=SMT.ask(1,1,cnt,L[q[i].p[j].second],R[q[i].p[j].second])/2;
    }

    for(int i=1;i<=pos;i++) printf("%d\n",ans[i]);
    system("pause");
    return 0;
}