鼹鼠们在底下开凿了n个洞，由n-1条隧道连接，对于任意的i>1，第i个洞都会和第i/2（取下整）个洞间有一条隧
道，第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠，第i只鼹鼠住在第pi个洞内，一天早晨，前k只
鼹鼠醒来了，而后n-k只鼹鼠均在睡觉，前k只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的ci均大
于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的1<=k<=m，输出最小的鼹鼠行动
路径的总长度，保证一定存在某种合法方案。
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[100010];
int g[100010];
int v[100010][2];
int ans;
int n,m;
int x,mn;
int c[100010];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
memset(f,0x3f,sizeof(f));
for(int i=n;i>=1;i--)
{
if(c[i])
{
f[i]=0,g[i]=i;
}
if(f[i]+1<f[i>>1])
{
f[i>>1]=f[i]+1,g[i>>1]=g[i];
}
}
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
int pos,anc,sum=0;
mn=1<<30;
for(int i=x;i;i>>=1)
{
if(mn>f[i]+sum)
{
mn=f[i]+sum,pos=g[i],anc=i;
}
sum+=v[i][0]>=0?1:-1;
}
ans+=mn;
c[pos]--;
printf("%d",ans);
if(j!=m)printf(" ");
for(int i=x;i!=anc;i>>=1)
{
v[i][0]<0?v[i][0]++:v[i][1]--;
}
for(int i=pos;i!=anc;i>>=1)
{
v[i][1]<0?v[i][1]++:v[i][0]--;
}
for(int i=x;i!=anc;i>>=1)
{
f[i]=1<<30;
if(c[i]&&f[i]>0)
{
f[i]=0,g[i]=i;
}
if((i<<1)<=n&&f[i<<1]+(v[i<<1][1]>=0?1:-1)<f[i])
{
f[i]=f[i<<1]+(v[i<<1][1]>=0?1:-1),g[i]=g[i<<1];
}
if((i<<1|1)<=n&&f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1)<f[i])
{
f[i]=f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1),g[i]=g[i<<1|1];
}
}
for(int i=pos;i;i>>=1)
{
f[i]=1<<30;
if(c[i]&&f[i]>0)
{
f[i]=0,g[i]=i;
}
if((i<<1)<=n&&f[i<<1]+(v[i<<1][1]>=0?1:-1)<f[i])
{
f[i]=f[i<<1]+(v[i<<1][1]>=0?1:-1),g[i]=g[i<<1];
}
if((i<<1|1)<=n&&f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1)<f[i])
{
f[i]=f[i<<1|1]+(v[i<<1|1][1]>=0?1:-1),g[i]=g[i<<1|1];
}
}
}
}
BZOJ4849[Neerc2016]Mole Tunnels——模拟费用流+树形DP
原文：https://www.cnblogs.com/Khada-Jhin/p/10428986.html