神奇的树形dp系列
先看一下题目给出的条件：
1、完全二叉树
2、任意时刻点亮的灯泡必须连通
3、点亮一个灯泡后必须先点亮其子树
那么点亮灯泡的过程就类似这样：
点亮灯泡k,点亮它的一个子树，再点亮它另外的子树，
然后回到k的父节点，点亮fa之后再点亮fa的其他子树……
所以对于一个节点u，有这样两种情况:
u还没有被点亮，则下一个被点亮的一定是它的儿子
u是叶子节点，在下一个被点亮的一定是它的某一级祖先，或者是它某一级祖先的儿子
我们定义dp数组f和g
f[i][j]表示点亮i之后回到i的第j个祖先的最小花费
g[i][j]表示点亮i之后回到i的第j个祖先的另一个儿子的最小花费
然后从下到上，由儿子的状态转移到父亲的状态
注意讨论当前节点的儿子个数。
最后统计答案时，根据点亮的过程累加即可。
ps:由于这是一棵完全二叉树，所以可以不用递归的方式dfs
直接预处理出每个节点的儿子和它到各级祖先的距离，用循环转移即可。
此题数据贼大，所以最终答案ans的初值一定要开大！
丑陋的代码：
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,num,w[N],fa[N],ls[N],rs[N];
ll f[N][20];//f表示i是亮的，回到i的第j个祖先的最小花费
ll g[N][20];//g表示i是亮的，回到i的第j个祖先的另一个儿子的最小花费
ll dis[N][20];//dis表示从i到i的第j个祖先的距离
ll ans=1e17;
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline int brother(int k,int x)//k的第x个祖先的另一个儿子
{
return (k>>(x-1))^1;
}
inline ll getans()
{
for (reg int k=n;k>=1;k--)
{
if (!ls[k])//k为叶子节点
for (reg int i=1;k>>(i-1);i++)
g[k][i]=(dis[k][i]+dis[brother(k,i)][1])*w[brother(k,i)];
else if (!rs[k])//k只有左儿子
for (reg int i=1;k>>(i-1);i++)
g[k][i]=dis[ls[k]][1]*w[ls[k]]+g[ls[k]][i+1];
else//k有两个儿子
for (reg int i=1;k>>(i-1);i++)
g[k][i]=min(dis[ls[k]][1]*w[ls[k]]+g[ls[k]][1]+g[rs[k]][i+1],dis[rs[k]][1]*w[rs[k]]+g[rs[k]][1]+g[ls[k]][i+1]);
}
for (reg int k=n;k>=1;k--)
{
if(!ls[k])
for (reg int i=1;k>>(i-1);i++)
f[k][i]=dis[k][i]*w[k>>i];
else if (!rs[k])
for (reg int i=1;k>>(i-1);i++)
f[k][i]=f[ls[k]][i+1]+dis[ls[k]][1]*w[ls[k]];
else
for (reg int i=1;k>>(i-1);i++)
f[k][i]=min(dis[ls[k]][1]*w[ls[k]]+g[ls[k]][1]+f[rs[k]][i+1],dis[rs[k]][1]*w[rs[k]]+g[rs[k]][1]+f[ls[k]][i+1]);
}
for (reg int k=1;k<=n;k++)
{
reg ll sum=f[k][1];
for (reg int i=1,fa=k>>1;fa;++i,fa>>=1)
{
reg int bro=brother(k,i);
if (bro>n) sum+=dis[fa][1]*w[fa>>1];
else sum+=dis[bro][1]*w[bro]+f[bro][2];
}
ans=min(ans,sum);
}
return ans;
}
int main()
{
n=read();
for (reg int i=1;i<=n;w[i++]=read());
for (reg int i=2;i<=n;i++) dis[i][1]=(ll)read();
for (reg int i=1;i<=(n>>1)+1;i++)//完全二叉树
{
if ((i<<1)<=n) ls[i]=(i<<1);
else break;
if ((i<<1|1)<=n) rs[i]=(i<<1|1);
}
for (reg int i=2;i<=18;i++)
for (reg int k=n;k>>i;k--)
dis[k][i]=dis[k][i-1]+dis[k>>(i-1)][1];
printf("%lld\n",getans());
return 0;
}
```