题目描述

输入

输出

样例输入

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #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
          
           =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