【NOIP2016提高A组五校联考1】排队

题目

Description

Input

Sample Input

5 4
1 2
1 3
3 4
3 5
1 4
2 4
1 2
2 5

Output

Sample Output

3
1
1
2

Data Constraint

Hint

比赛时の想法

暴力啊QAQ~~~~

正解

首先我们预处理出每一个点的优先级，就是下一个走进来的人会走到当前优先级最小的那个点，那么我们可以用一个堆来维护，每一次进一个人就出一次堆
对于操作2，我们可以用倍增来找到当前位置上面的一个最接近根节点的一个有人的节点，那么就等于这个节点的人直接走到删除的那个节点那里去了
注意在操作2完了之后要维护一下堆
那么两个操作都是log级别的

贴代码

var
    tree,s,ls:array[0..200005]of longint;
    f:array[0..100005,0..18]of longint;
    a,b:array[0..200005,1..2]of longint;
    cp:array[0..20]of longint;
    bz:array[0..100005]of boolean;
    i,j,k,l,m,n,t,x,y,cy,o,p:longint;
procedure qsort(l,r:longint);
var
    i,j,mid,mid1:longint;
begin
    i:=l;
    j:=r;
    mid:=a[(i+j) div 2,1];
    mid1:=a[(i+j) div 2,2];
repeat
while (a[i,1]<mid) or ((a[i,1]=mid) and (a[i,2]<mid1)) do inc(i);
while (a[j,1]>mid) or ((a[j,1]=mid) and (a[j,2]>mid1)) do dec(j);
if i<=j then
begin
            a[0]:=a[i];
            a[i]:=a[j];
            a[j]:=a[0];
            inc(i);
            dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure star;
begin
    b[a[1,1],1]:=1;
for i:=2 to 2*n-2 do
if a[i,1]<>a[i-1,1] then
begin
        b[a[i-1,1],2]:=i-1;
        b[a[i,1],1]:=i;
end;
    b[a[2*n-2,1],2]:=2*n-2;
end;
procedure dfss(x:longint);
var
    i:longint;
begin
    bz[x]:=true;
for i:=b[x,1] to b[x,2] do
if (i<>0) and (bz[a[i,2]]=false) then
begin
        f[a[i,2],0]:=x;
        dfss(a[i,2]);
end;
    inc(cy);
    tree[cy]:=x;
    s[x]:=cy;
end;
procedure down(x:longint);
begin
if (s[tree[x*2]]<s[tree[x]]) and (s[tree[x*2]]<s[tree[x*2+1]]) then
begin
        tree[0]:=tree[x];
        tree[x]:=tree[x*2];
        tree[x*2]:=tree[0];
        down(x*2);
end else
if s[tree[x*2+1]]<s[tree[x]] then
begin
        tree[0]:=tree[x*2+1];
        tree[x*2+1]:=tree[x];
        tree[x]:=tree[0];
        down(x*2+1);
end;
end;
procedure up(x:longint);
begin
if x=1 then exit;
if s[tree[x div 2]]>s[tree[x]] then
begin
        tree[0]:=tree[x div 2];
        tree[x div 2]:=tree[x];
        tree[x]:=tree[0];
        up(x div 2);
end;
end;
procedure lca;
var
    i,j:longint;
begin
for j:=1 to 18 do
for i:=1 to n do
            f[i,j]:=f[f[i,j-1],j-1];
end;
begin
    assign(input,'t3.in'); reset(input);
    readln(n,t);
for i:=1 to n-1 do
begin
        readln(a[i,1],a[i,2]);
        a[i+n-1,1]:=a[i,2];
        a[i+n-1,2]:=a[i,1];
end;
    qsort(1,2*n-2);
    star;
    cy:=0;
    dfss(1);
    cy:=n;
    s[0]:=maxlongint;
    lca;
for i:=1 to n do up(i);
    cp[0]:=1;
for i:=1 to 18 do cp[i]:=cp[i-1]*2;
    fillchar(bz,sizeof(bz),false);
for i:=1 to t do
begin
        readln(o,p);
if o=1 then
for j:=1 to p do
begin
if j=p then writeln(tree[1]);
            bz[tree[1]]:=true;
            tree[1]:=0;
            down(1);
end else
begin
            k:=0;
while f[p,k]>0 do inc(k);
            dec(k);
            x:=p;
            y:=0;
for j:=k downto 0 do
if (f[x,j]>0) and (bz[f[x,j]]=true) then
begin
                x:=f[x,j];
                y:=y+cp[j];
end;
for j:=cy downto 1 do
if tree[j]=0 then break;
            tree[j]:=x;
            bz[x]:=false;
            up(j);
            writeln(y);
end;
end;
    close(input);
end.