我们充分发扬人类智慧

· · 题解

P4253 [SCOI2015] 小凸玩密室

考虑你的操作：首先选个点，把子树开完然后开父亲再把父亲另一个子树开完，以此类推。

子树操作就是先走到叶子然后再返回去一路上开另一个子树的灯泡，有点子问题的雏形了，然后注意完美二叉树可以做 O(\sum siz) 的做法。

设 f_{u,v} 表示开始的点在 u 子树外或 u，点完 u 子树内的点，最后点的是 v 的最小代价，这里 v 的取值只有子树内的叶子。

\begin{aligned} &f_{u,rp}=\min_{lp} (a_{ls}dis(u,ls)+a_{rs}dis(lp,rs)+f_{ls,lp})+f_{rs,rp}\\ &f_{u,lp}=\min_{rp} (a_{rs}dis(u,rs)+a_{ls}dis(rp,ls)+f_{rs,rp})+f_{ls,lp} \end{aligned}

这个东西能做从根出发的答案，即最先走 u 的答案，考虑起点在 u 子树内的情况，设 g_{u,v} 表示起点在 u 子树内，点完 u 子树内的点，结束点在 v 的方案数，这里结束点是叶子或者儿子节点，初值即出发点就是 u 的时候 g_{u,v}=f_{u,v}，否则考虑在儿子子树内：

\begin{aligned} &g_{u,rp}=\min_{lp} (a_{u}dis(lp,u)+g_{ls,lp})+f_{rs,rp}+a_{rs}dis(u,rs)\\ &g_{u,lp}=\min_{rp} (a_{u}dis(rp,u)+g_{rs,rp})+f_{ls,lp}+a_{ls}dis(u,ls) \end{aligned}

前面都是假设没有二度链的情况，注意二度链最后停下的位置不一定是叶子而是链的一端，不好的是，n 为偶数的时候都有二度链，我们有解决办法吗，当然这就简单了，我们充分发挥人类智慧，你加一个点权为 +\inf，父亲边权为 0 的虚拟叶子即可，不难发现这样除了根是二度点之外，只有一度的叶子和三度的中转点，不会有只有一个儿子的点，而且答案不会变。（因为这题的答案比较大，在 \inf=10^{18} 之后只能用 __int128 了）

#define LL __int128
const int N=2e5+100;
int n,fa[N],w[N];
LL a[N];
LL dep[N];
vector<int> E[N];
vector<LL> f[N],g[N],lf[N];
void DP(int u){
//  cerr<<"! "<<u<<endl;
    if(!E[u].size()){
        lf[u].pb(u),f[u].pb(0),g[u].pb(0);
    }
    else{
        int ls=E[u][0],rs=E[u][1];
        DP(ls),DP(rs);
        int szl=lf[ls].size(),szr=lf[rs].size();
        lf[u].resize(szl+szr),f[u].resize(szl+szr),g[u].resize(szl+szr);
        LL mfl=INF,mfr=INF,mgl=INF,mgr=INF;
        rep(i,0,szl-1) {
            mfl=min(mfl,a[ls]*(dep[ls]-dep[u])+a[rs]*(dep[lf[ls][i]]+dep[rs]-2ll*dep[u])+f[ls][i]);
            mgl=min(mgl,a[u]*(dep[lf[ls][i]]-dep[u])+g[ls][i]);
        }
        rep(i,0,szr-1){
            mfr=min(mfr,a[rs]*(dep[rs]-dep[u])+a[ls]*(dep[lf[rs][i]]+dep[ls]-2ll*dep[u])+f[rs][i]);
            mgr=min(mgr,a[u]*(dep[lf[rs][i]]-dep[u])+g[rs][i]);
        } 
        rep(i,0,szl-1) {
            lf[u][i]=lf[ls][i];
            f[u][i]=f[ls][i]+mfr;
            g[u][i]=min(f[u][i],f[ls][i]+a[ls]*(dep[ls]-dep[u])+mgr);
        }
        rep(i,0,szr-1) {
            lf[u][i+szl]=lf[rs][i];
            f[u][i+szl]=f[rs][i]+mfl;
            g[u][i+szl]=min(f[u][i+szl],f[rs][i]+a[rs]*(dep[rs]-dep[u])+mgl);
        }
    }
}
signed main(){
    bool fl=0;
    read(n);if(n%2==0) fl=1;
    rep(i,1,n) read(a[i]);
    rep(i,2,n) read(w[i]);
    if(fl)++n,w[n]=0,a[n]=1e18;//特判为偶数出现二度链的情况 
    rep(i,2,n) fa[i]=i/2,dep[i]=dep[fa[i]]+w[i],E[fa[i]].pb(i);
    DP(1);
    LL ans=INF;
    for(auto i:g[1]) ans=min(ans,i);
    write(ans,'\n');
    return 0;
}