题目描述

输入

输出

样例输入

5 4

1 2

1 3

3 4

3 5

1 4

2 4

1 2

2 5

样例输出

3

1

1

2

数据范围

样例解释

解法

可推知原树可以转换为一个序列，即优先序列：

一个01序列，当要往其中加入元素时，给第一个0加1即可。

操作1

等价于所谓优先序列加入元素。

实现：

二分第一个0的位置index；

使用数据结构得出[1,index]的和sum，如果index−sum>0，则index合法。

操作2

利用倍增得出最近的连续的有值祖先v，给v－1即可。

时间复杂度为O(nlogn2)。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="aP3.in";

const char* fout="aP3.out";

const int inf=0x7fffffff;

const int maxn=100007,maxm=maxn*2,maxk=20;

int n,m,i,j,k,tot,ans;

int fi[maxm],la[maxm],ne[maxm];

int a[maxn],de[maxn],fa[maxn][maxk];

int b[maxn],c[maxn],dfn[maxn],st[maxn],en[maxn];

int ta[maxn];

void change(int v,int v1){

    for (;v<=n;v+=v&-v) ta[v]+=v1;

}

int presum(int v){

    int v1=0;

    for (;v;v-=v&-v) v1+=ta[v];

    return v1;

}

int getsum(int l,int r){

    return presum(r)-presum(l-1);

}

void add_line(int a,int b){

    tot++;

    ne[tot]=fi[a];

    la[tot]=b;

    fi[a]=tot;

}

void build(int v,int from){

    int i,j,k;

    fa[v][0]=from;

    de[v]=de[from]+1;

    for (i=1,j=ln(de[v],2);i<=j;i++){

        k=fa[v][i-1];

        fa[v][i]=fa[k][i-1];

    }

    st[v]=b[0];

    for (k=fi[v];k;k=ne[k])

        if (la[k]!=from) b[++b[0]]=la[k];

    en[v]=b[0];

    if (en[v]-st[v]) sort(b+st[v]+1,b+en[v]+1);

    for (i=st[v]+1;i<=en[v];i++) build(b[i],v);

    c[++c[0]]=v;

    dfn[v]=c[0];

}

int add(){

    int l=1,r=n,mid;

    while (l<r){

        mid=(l+r)/2;

        if (mid-presum(mid)) r=mid;

        else l=mid+1;

    }

    a[c[l]]=1;

    change(l,1);

    return c[l];

}

int del(int v){

    int i,j,k=v;

    if (a[k]==0) return 0;

    for (i=ln(de[v],2);i>=0;i--){

        if (a[fa[k][i]]) k=fa[k][i];

    }

    if (a[fa[k][0]]) k=fa[k][0];

    a[k]=0;

    change(dfn[k],-1);

    return de[v]-de[k];

}

int main(){

    scanf("%d%d",&n,&m);

    for (i=1;i<n;i++){

        scanf("%d%d",&j,&k);

        add_line(j,k);

        add_line(k,j);

    }

    build(1,0);

    for (i=1;i<=m;i++){

        scanf("%d%d",&j,&k);

        if (j==1){

            for (;k;k--) ans=add();

        }else{

            ans=del(k);

        }

        printf("%d\n",ans);

    }

    return 0;

}