题目 当然，根固定为 1 1 1，但是第一个被点亮的灯不一定是 1 1 1。
这里我只会讲最终做法，但是如果你要问这个结果到底是怎么得到的，其中的心路历程是什么，这篇博客：https://www.luogu.com.cn/blog/MachineryCountry/solution-p4253相信能给你不错的体验。
首先，我们先观察叶子节点，一个叶子节点，跑完之后，要么点亮其的一个祖先（会出现这种情况一般是因为第一个被点亮的灯不是 1 1 1），要么点亮其祖先的另外一个儿子，推广发现每一个点在遍历完其子树后，都是这种情况。
又发现，完全二叉树有一个极其优美的性质，树的高度为 l o g n logn logn层。
不妨考虑 f i , j f_{i,j} fi,j表示第 i i i个子树遍历完之后点亮的是第 j + 1 j+1 j+1个祖先的最小花费， g i , j g_{i,j} gi,j则是第 j + 1 j+1 j+1个祖先的一个儿子的最小花费。
g i , j = m i n ( a l c ∗ b l c + g l c , 0 + g r c , j + 1 , a r c ∗ b r c + g r c , 0 + g l c , j + 1 ) g_{i,j}=min(a_{lc}*b_{lc}+g_{lc,0}+g_{rc,j+1},a_{rc}*b_{rc}+g_{rc,0}+g_{lc,j+1}) gi,j=min(alc∗blc+glc,0+grc,j+1,arc∗brc+grc,0+glc,j+1) f i , j = m i n ( a l c ∗ b l c + g l c , 0 + f r c , j + 1 , a r c ∗ b r c + g r c , 0 + f l c , j + 1 ) f_{i,j}=min(a_{lc}*b_{lc}+g_{lc,0}+f_{rc,j+1},a_{rc}*b_{rc}+g_{rc,0}+f_{lc,j+1}) fi,j=min(alc∗blc+glc,0+frc,j+1,arc∗brc+grc,0+flc,j+1)
其余的状态方程就不列了，比较麻烦。
我还专门设置了 t i t_{i} ti表示遍历 i i i的子树的花费。
至于第一个点亮谁暴力枚举， l o g n logn logn的时间能算出第一个点亮某个点的最小花费。
但是需要注意的是，不管是 f , g , t f,g,t f,g,t， i i i号点被点亮的费用都是没有算进去的，因为遍历 i i i的子树，其子树内的点 x x x肯定都是从另外一个 i i i子树内的点 y y y出发去亮 x x x的，因此可以树形 D P DP DP直接计算，但是 x x x不一样， x x x是灵活应变的，只有外面知道他是被哪个点点亮的，而树形DP基本上只能处理子树内的点，所以只能不算点亮 x x x的花费。（事实上，也正是因为树形DP只能处理子树内的点，所以从 i i i子树出来到达的点还必须多设置一维来处理）
但是为什么谁点亮 x x x不用设置一个维去处理呢？因为要么用 f , g f,g f,g已经算完了点亮 x x x的花费，要么就是直接父亲更新，所以不用特殊设置。
那可不可以设置一维来处理谁点亮 x x x，然后就不用设置一维来处理 x x x子树后第一个点亮谁，事实上也是可以的，只要利用好前面讲的每个子树遍历完后要么点亮其的一个祖先，要么点亮其祖先的另外一个儿子的性质即可，但是子树的叶子节点的信息往往比祖先信息更加的难以维护和统计，所以代码吗，也就有亿点长和亿点难打吧，但是应该（我猜）也是可以的，应该也是 n l o g n nlogn nlogn。但是代码真的是太难处理了
时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn).
其实我的代码打复杂了，如果想要看代码好看一些的可以去你谷的题解区看看，里面的许多代码都写的比我优美。
#include<cstdio> #include<cstring> #define N 210000 #define SN 20 //17 using namespace std; typedef long long LL; template<class T> inline T mymin(T x,T y){return x<y?x:y;} template<class T> inline T mymax(T x,T y){return x>y?x:y;} int fa[N][SN],other[N]/*另外一个儿子*/,n; LL f[N][SN],g[N][SN],dis[N],a[N],b[N],t[N]; void dfs(int x) { for(int i=1;i<=17;i++) { fa[x][i]=fa[fa[x][0]][i-1]; if(!fa[x][i])break; } for(int i=0;i<=1;i++) { int y=(x<<1)+i; if(y>n)continue; dis[y]=dis[x]+b[y];fa[y][0]=x; } for(int i=0;i<=1;i++) { int y=(x<<1)+i; if(y>n)continue; other[x]=y^1;//另外一个儿子 dfs(y); } for(int i=0;i<=17;i++) { if(!fa[x][i])break; if((x<<1)>n) { g[x][i]=(dis[other[fa[x][i]]]+dis[x]-2*dis[fa[x][i]])*a[other[fa[x][i]]]; f[x][i]=(dis[x]-dis[fa[x][i]])*a[fa[x][i]]; } else if((x<<1)==n)//只有一个儿子 { int lc=x<<1; g[x][i]=b[lc]*a[lc]+g[lc][i+1]; f[x][i]=b[lc]*a[lc]+f[lc][i+1]; } else//两个儿子都有 { int lc=x<<1,rc=(x<<1)+1; g[x][i]=mymin(b[lc]*a[lc]+g[lc][0]+g[rc][i+1],b[rc]*a[rc]+g[rc][0]+g[lc][i+1]); f[x][i]=mymin(b[lc]*a[lc]+g[lc][0]+f[rc][i+1],b[rc]*a[rc]+g[rc][0]+f[lc][i+1]); } } if((x<<1)>n)t[x]=0; else if((x<<1)==n)t[x]=t[x<<1]+b[x<<1]*a[x<<1]; else { int lc=x<<1,rc=(x<<1)+1; t[x]=mymin(b[lc]*a[lc]+g[lc][0]+t[rc],b[rc]*a[rc]+g[rc][0]+t[lc]); } } inline int pd_son(int x,int f){return (f<<1)==x?0:1;} LL solve(int x)//假设x为根，且x不是1号点 { LL ans=f[x][0]; int ff=(x>>1); while(ff>1) { int y=x^1/*x的兄弟*/; if(y>n/*x是ff的唯一儿子*/)ans+=b[ff]*a[ff>>1]; else ans+=f[y][1]+a[y]*b[y]; x=ff;ff=(x>>1); } int y=x^1/*x的兄弟*/; if(y<=n/*x是ff的唯一儿子*/)ans+=t[y]+a[y]*b[y]; return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=2;i<=n;i++)scanf("%lld",&b[i]); dfs(1); LL ans=t[1]; for(int i=2;i<=n;i++) { ans=mymin(ans,solve(i)); } printf("%lld\n",ans); return 0; }