传送门
题意简述：
给一棵完全二叉树，有点权aia_iai和边权，每个点有一盏灯，现在要按一定要求点亮：
- 任意时刻点亮的灯泡必须连通
- 点亮一个灯泡后必须先点亮其子树
费用计算如下：点第一盏灯不要花费，之后如果点一盏灯uuu，且上一盏点的是vvv，花费是au∗distu,va_u*dist_{u,v}au∗distu,v
问把所有点都点亮的最小花费。
思路：树形dpdpdp好题。
考虑到把一棵子树点亮之后要么点亮它的某个祖先，要么点亮它的某个祖先的兄弟。
记f0/1,i,jf_{0/1,i,j}f0/1,i,j表示把iii这棵子树全部点亮之后，把iii的jjj级祖先/iii的j−1j-1j−1级祖先的兄弟 点亮的最小总花费。
然后就可以随便转移了。
最后统计答案的时候注意细节。
代码：
#include<bits/stdc++.h>
#define ri register int
#define idx(x,y) (((1<<((y)-1))<=(x))?(x)>>(y):-1)
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=2e5+5;
typedef long long ll;
const ll inf=1e18;
int n,a[N];
ll dis[N][18],f[2][N][18],ans=inf;
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=2;i<=n;++i){
dis[i][1]=read();
for(ri j=2;~idx(i,j);++j)dis[i][j]=dis[i][1]+dis[i>>1][j-1];
}
for(ri p=n;p;--p){
for(ri d=1;~idx(p,d);++d){
f[0][p][d]=f[1][p][d]=inf;
if(lc>n){
f[0][p][d]=dis[p][d]*a[idx(p,d)];
f[1][p][d]=(dis[p][d]+dis[idx(p,d-1)^1][1])*a[idx(p,d-1)^1];
}
else if(rc>n){
f[0][p][d]=f[0][lc][d+1]+dis[lc][1]*a[lc];
f[1][p][d]=f[1][lc][d+1]+dis[lc][1]*a[lc];
}
else{
f[0][p][d]=min(f[1][lc][1]+f[0][rc][d+1]+dis[lc][1]*a[lc],f[1][rc][1]+f[0][lc][d+1]+dis[rc][1]*a[rc]);
f[1][p][d]=min(f[1][lc][1]+f[1][rc][d+1]+dis[lc][1]*a[lc],f[1][rc][1]+f[1][lc][d+1]+dis[rc][1]*a[rc]);
}
}
}
for(ri s=1;s<=n;++s){
ll tmp=f[0][s][1];
for(ri p=s>>1,pre=s;~p;p=idx(p,1),pre>>=1){
if((pre^1)<=n)tmp+=dis[pre^1][1]*a[pre^1]+f[0][pre^1][2];
else tmp+=dis[p][1]*a[p>>1];
}
ans=min(ans,tmp);
}
cout<<ans;
return 0;
}