「SCOI2015」小凸玩密室 解题报告

「SCOI2015」小凸玩密室

虽然有心里在想一些奇奇怪怪的事情的原因，不过还是写太久了..

不过这个题本身也挺厉害的

注意第一个被点亮的是任意选的，我最开始压根没注意到

\(dp_{i,j}\)代表\(i\)号点子树最后连出去的一个点连的是它第\(j\)层的祖先

\(f_{i,j}\)代表\(i\)号点子树最后连出去的一个点连的是它第\(j\)层祖先的另一个儿子

然后我们就可以拼子树，做换根了

要讨论只有一个儿子的情况

---

Code:

#include <cstdio>

#include <cstring>

#include <cctype>

#include <algorithm>

#define ll long long

const int N=2e5+10;

using std::min;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

ll dp[2][N][20],a[N],edge[N],ans=1e18;

int n,Log[N];

#define ls (id<<1)

#define rs (id<<1|1)

void dfs(int id)

{

	if(id<<1>n) return;

	dfs(ls),dfs(rs);

	for(int dep=Log[id];~dep;dep--)

    {

        if(ls<=n&&rs<=n)

        {

            dp[0][id][dep]=min(a[ls]*edge[ls]+dp[1][ls][Log[id]]+dp[0][rs][dep]

                              ,a[rs]*edge[rs]+dp[1][rs][Log[id]]+dp[0][ls][dep]);

            dp[1][id][dep]=min(a[ls]*edge[ls]+dp[1][ls][Log[id]]+dp[1][rs][dep]

                              ,a[rs]*edge[rs]+dp[1][rs][Log[id]]+dp[1][ls][dep]);

        }

        else if(ls<=n)

        {

            dp[0][id][dep]=a[ls]*edge[ls]+dp[0][ls][dep];

            dp[1][id][dep]=a[ls]*edge[ls]+dp[1][ls][dep];

        }

    }

}

void dfs0(int id,ll cost)

{

    ans=min(ans,dp[0][id][Log[id]-1]+cost);

    if(ls<=n&&rs<=n)

    {

        dfs0(ls,a[rs]*edge[rs]+dp[0][rs][Log[id]-1]+cost);

        dfs0(rs,a[ls]*edge[ls]+dp[0][ls][Log[id]-1]+cost);

    }

    else if(ls<=n)

        dfs0(ls,edge[id]*a[id>>1]+cost);

}

int main()

{

	int flag=0;read(n);

	for(int i=1;i<=n;i++) read(a[i]),Log[i]=Log[i>>1]+1;

	for(int i=2;i<=n;i++) read(edge[i]);

	memset(dp,0x3f,sizeof dp);

	for(int i=1;i<=n;i++)

		if(i<<1>n)

		{

			int typ=!(i&1),id=i>>1;ll sum=edge[i];

			for(int j=Log[i]-1;~j;j--)

			{

				dp[0][i][j]=a[id]*sum;

				dp[1][i][j]=a[id<<1|typ]*(sum+edge[id<<1|typ]);

				sum+=edge[id];

				typ=!(id&1);

				id>>=1;

			}

		}

	dfs(1);

	dfs0(1,0);

	printf("%lld\n",ans);

	return 0;

}

---

2019.2.27