来自FallDream的博客，未经允许，请勿转载，谢谢
貌似是省队集训女队讲的题。。。
今天在bzoj找一道题无果，但是翻到了这道就顺便写了下。
鼹鼠们在底下开凿了n个洞，由n-1条隧道连接，对于任意的i>1，第i个洞都会和第i/2（取下整）个洞间有一条隧道，第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠，第i只鼹鼠住在第pi个洞内，一天早晨，前k只鼹鼠醒来了，而后n-k只鼹鼠均在睡觉，前k只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的ci均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的1<=k<=m，输出最小的鼹鼠行动路径的总长度，保证一定存在某种合法方案。
n<=10^5
看出是完全二叉树上费用流 建图比较简单 但是并不能过
发现树高是log级别的，所以考虑直接手动模拟。
f[x]表示从x走到子树中的一个可以觅食的点的最短距离，顺便记一下是哪个点。
一条边记一下它的正向通过次数和反向通过次数，如果他们相同那么两条边的距离都是1，不然有一个方向会因为反向边而变成-1
然后直接枚举lca更新答案，并且更新通过次数和f数组即可。
复杂度nlogn
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 100000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,p[MN+],tms[MN+],f[MN+],From[MN+],ans=;
inline int GetU(int x){return tms[x]<=?:-;}
inline int GetD(int x){return tms[x]>=?:-;}
void update(int x)
{
int l=x<<,r=x<<|;
if(p[x]) f[x]=,From[x]=x;
else
{
f[x]=1e9,From[x]=;
if(l<=n&&f[l]+GetD(l)<f[x]) f[x]=f[l]+GetD(l),From[x]=From[l];
if(r<=n&&f[r]+GetD(r)<f[x]) f[x]=f[r]+GetD(r),From[x]=From[r];
}
} int main()
{
n=read();m=read();
for(int i=;i<=n;++i) p[i]=read();
for(int i=n;i;--i) update(i);
for(int i=;i<=m;++i)
{
int x=read(),mn=f[x],Best=x,d=;
for(int t=x;t>;t>>=)
if(f[t>>]+(d+=GetU(t))<mn)
mn=f[t>>]+d,Best=t>>;
printf("%d ",ans+=mn);--p[From[Best]];
for(int i=From[Best];i>Best;i>>=)
++tms[i],update(i);
for(int i=x;i>Best;i>>=)
--tms[i],update(i);
for(int i=Best;i;i>>=) update(i);
}
return ;
}