DTOJ 1430:ballmachine（ballmachine）
【题目描述】
我们有一个可视为有根树的“ball machine”。这棵树的节点编号从1到N。每个节点只能为空或者包含一个球。最初，所有的节点都是空的。在机器运行的时候，这台机器可以执行两种不同类型的操作：
1、机器添加K个球：把球逐个放入根节点。只要这个球正下方有一个空的节点，它会滚下来。如果有多个空的子节点，球会选择其中子树数字最小的节点并滚到该节点。因此，如果球滚下多次，它会在每层都分别进行选择。例如：如果我们将在如下所示的机器中添加两个球，他们将依次滚到节点1和3：第一个球从节点4滚到节点3因为节点3是空的，它将进一步地从节点3到节点1。第二球从节点4滚到节点3，并停在那里。
2、从一个指定的节点取出一个球：该节点变成空，如果上面有球，则球会从上面滚下来。每当一个空节点的父节点包含一个球，这个球会滚下来。如果我们在下图所示的机器中，从机器删除从节点5，节点7和节点8的球（按照这个顺序）那么，节点1，2和3将成为空的。
【输入】
第一行包含两个整数N和Q ，表示树的节点数和操作的次数。接下来的N行描述了这台ball machine。每一行都包含一个整数，第i个数描述的是第i个节点的父亲，第i个数为0则表示这个节点为根节点。接下来的Q行，每一行包含两个整数，描述一个所要执行的操作。一个类型1的操作是指指令符1 k，其中k指被添加到这台机器的球的数量。一个类型2的操作是指指令符2 x，其中x指需要从第x个节点中移除一个球。这里能保证所有执行的操作是正确的，即添加球的数目不会多于当前的空节点数，且不会从一个空的节点中删除一个球。
【输出】
对于每个类型1的操作，输出所添加的最后一个球最后停止的节点编号。 对于每个类型2的操作，输出删除该球后发生滚动的球的数目。
【样例输入】
8 4012233461 82 52 72 8
【样例输出】
1322
【分析】
操作1：先dfs一遍，依题意构成一个插入序列，每次插入序列的最左侧的空位，用一个set维护。 操作2：倍增直接算。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
inline int read ( void )
{
int x=0;char ch=getchar();
while ( !isdigit(ch) ) ch=getchar();
while ( isdigit(ch) ) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
set<int> s;vector<int> son[maxn];bool vis[maxn];
int rt[maxn],dfx[maxn],dfn,p[maxn][20],n,q,root,dep[maxn],mp[maxn],f[maxn];
inline bool cmp ( const int &x,const int &y ) { return f[x]<f[y]; }
inline void dfs1 ( int u )
{
dep[u]=dep[rt[u]]+1;p[u][0]=rt[u];f[u]=u;
for ( int i=0;i<son[u].size();i++ ) dfs1(son[u][i]),f[u]=min(f[u],f[son[u][i]]);
}
inline void dfs2 ( int u )
{
sort(son[u].begin(),son[u].end(),cmp);
for ( int i=0;i<son[u].size();i++ ) dfs2(son[u][i]);
dfx[++dfn]=u;mp[u]=dfn;
}
int main()
{
n=read();q=read();memset(p,-1,sizeof(p));
for ( int i=1;i<=n;i++ ) s.insert(i);
for ( int i=1;i<=n;i++ )
{
scanf("%d",&rt[i]);
if ( !rt[i] ) root=i;
else son[rt[i]].push_back(i);
}
dfs1(root);dfs2(root);
for ( int j=1;j<=19;j++ )
for ( int i=1;i<=n;i++ )
if ( p[i][j-1]!=-1 ) p[i][j]=p[p[i][j-1]][j-1];
while ( q-- )
{
int opt=read(),x=read();
if ( opt==1 )
{
for(int i=1;i<=x;++i)
{
int tmp=*s.begin();
s.erase(tmp);vis[dfx[tmp]]=true;
if ( i==x ) printf("%d\n",dfx[tmp]);
}
}
else
{
int tmp=x;
for ( int i=19;i>=0;i-- ) if ( vis[p[tmp][i]] ) tmp=p[tmp][i];
vis[tmp]=false;s.insert(mp[tmp]);
printf("%d\n",dep[x]-dep[tmp]);
}
}
return 0;
}
