题解 P3816 【[FJOI2017]树的平均路长问题】
shadowice1984
2018-05-07 21:53:25
# 打表是不行的！
~~我就是N!爆搜，爆零，写$O(n^2)$暴力也绝对不打表！~~
~~打表是不可能打表的，这辈子都不可能打表的……~~
事实上代码还是非常好写的……，但是推不出来结论就gg了
________________
## 本题题解
首先我们会发现这道题和红黑树这个数据结构没有任何关系……，所以我们可以考虑一个非常朴素的树形dp……(PS:如果你对红黑树足够了解的话会发现题目中描述的实际上是一只松弛红黑树，即去掉了根节点必须是黑的这个限制)
首先我们要最大化的式子是
## $\sum_{i=1}^{n}Dep_{i}$
如果我们分别考虑每一个边的贡献，那么我们会发现每一个i的父亲边在深度值的计算中恰好被算了$siz_{i}$次
所以我们要最大化的式子又可以写成
## $\sum_{i=1}^{n}size_{i}$
其实不应该加上1号节点点的size的，但是由于这里的1号节点深度为1，所以我们平常的边深度和这里的点深度之和刚好差了一个$size_{i}$因此我们要最大化的东西就是
## $\sum_{i=1}^{n}size_{i}$
那么如果足够熟练的话可以很快的列出这样的一个dp式子，直接无脑的求什么列什么就行了……
我们令$Dp_{i,j,k}(j \in {0,1})$表示$size$为$i$的一只红黑树，黑高为k，根节点颜色为j，0表示红，1表示黑，的最大$size$之和
那么我们由于这是一个二叉树，所以我们按照在二叉树上的dp的一般套路，枚举左儿子的size，从而右儿子的size就可以确定，从而转移起我们的dp
然后另外两个限制分别是黑高相等和不能有两个相邻的红色点条件，直接在转移式子里面表达就行了，推出来大概长这样……
## $Dp_{i,0,k}=(max_{p=0}^{i-1}Dp_{p,1,k}+Dp_{i-1-p,1,k})+i$
这个是红色点的式子，由于不可以有两个相邻的红色点因此全部由黑色的dp转移过来，然后我们这里暴力枚举了左儿子的$size=p$，另外由于是红点，所以黑高不变
对于黑点的dp则是下面这3个式子取max
## $(max_{p=0}^{i-1}Dp_{p,1,k-1}+Dp_{i-1-p,1,k-1})+i$
## $(max_{p=0}^{i-1}Dp_{p,0,k-1}+Dp_{i-1-p,1,k-1})+i$
## $(max_{p=0}^{i-1}Dp_{p,0,k-1}+Dp_{i-1-p,0,k-1})+i$
还是一样的枚举左儿子size，注意分下情况讨论左右儿子的颜色进行转移，因为自己是黑点所以我们是由黑高减1的状态转移过来的
最后无论如何总的size都会+i，所以加上i
然后我们冷静分析一波算法的复杂度，发现这个算法的复杂度是$O(n^2logn)$
似乎铁定会T飞啊……但是像本题rk1这种无脑打表的思路肯定是不可取的啊，因为这道题当年考试的时候不让打表。
所以我们需要一些一些奇技淫巧来帮我们手动加速转移……
_________________
假设你是一名julao，在即将AK之时输出了dp数组的最优转移点
这里先附上暴力打出dp数组的转移点的generator~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e4+10;
int dp[2][N][17];int fr[2][N][17];int ans[N];
int main()
{
for(int i=0;i<=100;i++)for(int k=0;k<=8;k++)dp[0][i][k]=dp[1][i][k]=-0x3f3f3f3f;
dp[1][0][0]=0;
for(int i=1;i<=100;i++)
{
for(int k=0;k<=8;k++)
{
for(int j=0;j<=i-1;j++)
{
if(dp[0][i][k]<dp[1][j][k]+dp[1][i-1-j][k])
{dp[0][i][k]=dp[1][j][k]+dp[1][i-1-j][k];fr[0][i][k]=j;}
}dp[0][i][k]+=i;
if(dp[0][i][k]>0)
printf("dp[%d][%d][%d]=%d:fr %d\n",0,i,k,dp[0][i][k],fr[0][i][k]);
}
for(int k=1;k<=8;k++)
{
for(int j=0;j<=i-1;j++)
{
if(dp[1][i][k]<dp[1][j][k-1]+dp[1][i-1-j][k-1])
{dp[1][i][k]=dp[1][j][k-1]+dp[1][i-1-j][k-1];fr[1][i][k]=j;}
if(dp[1][i][k]<dp[1][j][k-1]+dp[0][i-1-j][k-1])
{dp[1][i][k]=dp[1][j][k-1]+dp[0][i-1-j][k-1];fr[1][i][k]=j;}
if(dp[1][i][k]<dp[0][j][k-1]+dp[0][i-1-j][k-1])
{dp[1][i][k]=dp[0][j][k-1]+dp[0][i-1-j][k-1];fr[1][i][k]=j;}
}dp[1][i][k]+=i;
if(dp[1][i][k]>0)
printf("dp[%d][%d][%d]=%d:fr %d\n",1,i,k,dp[1][i][k],fr[1][i][k]);
}
}
for(int i=1;i<=100;i++)
{
for(int k=0;k<=8;k++)
{ans[i]=max(ans[i],dp[0][i][k]);ans[i]=max(ans[i],dp[1][i][k]);}
}return 0;
}
```
________________
这里我们截取了这张表的最后一小部分
$ dp[0][98][3]=582:fr 34$
$dp[0][98][4]=671:fr 15$
$dp[0][98][5]=631:fr 31$
$dp[1][98][4]=643:fr 7$
$dp[1][98][5]=683:fr 15$
$dp[1][98][6]=631:fr 31$
$dp[0][99][3]=589:fr 35$
$dp[0][99][4]=679:fr 15$
$dp[0][99][5]=641:fr 31$
$dp[1][99][4]=651:fr 7$
$dp[1][99][5]=693:fr 15$
$dp[1][99][6]=641:fr 31$
$dp[0][100][3]=594:fr 36$
$dp[0][100][4]=687:fr 15$
$dp[0][100][5]=649:fr 31$
$dp[1][100][4]=659:fr 7$
$dp[1][100][5]=702:fr 15$
$dp[1][100][6]=649:fr 31$
我们仔细观察会发现这个转移似乎非常的有规律……
具体来讲经过细致的观察我们会得到这样的规律
每个dp状态$i,j$有且仅有两个合理的转移点(显然可能变的转移维度只有i这一维了)
1.i-p,其中p为离i最接近的二的整次幂，且小于i
2.如果这个点是红点，那么转移点为$2^k-1$,否则是$2^{k-1}-1$
(打表真好用.gif)
然后我们根据这个决策唯一性优化，可以将转移强行加速到$O(1)$，这样我们就可以以$O(nlogn)$的速度轻松通过本题~
上代码
``` C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e4+10;
int dp[2][N][18];int tr[N];int ans[N];
int main()
{
for(int i=0;i<=N-10;i++)for(int k=0;k<=17;k++)dp[0][i][k]=dp[1][i][k]=-0x3f3f3f3f;
for(int i=2,k=1;i<=N-10;i++){if(k<<1<i){k<<=1;}tr[i]=k;}
for(int i=2;i<=N-10;i++){tr[i]=i-tr[i];}
dp[1][0][0]=0;//注意初始条件，哨兵只有黑色
for(int i=1;i<=N-10;i++)
{
for(int k=0;k<=17;k++)//按照唯二合法的转移点转移就行了
{
int tr1=(k==0)?0:(1<<k)-1;if(i-1>=tr1)
{
dp[0][i][k]=max(dp[1][tr1][k]+dp[1][i-tr1-1][k],dp[1][tr[i]][k]+dp[1][i-tr[i]-1][k]);
if(dp[0][i][k]<0){dp[0][i][k]=-0x3f3f3f3f;}else {dp[0][i][k]+=i;}//这里注意重置一下，避免爆inf
}int ret;tr1=(k==0)?0:(1<<(k-1))-1;
if(k>=1&&(i-1>=tr1))
{
ret=max(dp[1][tr1][k-1]+dp[1][i-tr1-1][k-1],dp[1][tr[i]][k-1]+dp[1][i-tr[i]-1][k-1]);
dp[1][i][k]=max(dp[1][i][k],ret);
ret=max(dp[0][tr1][k-1]+dp[1][i-tr1-1][k-1],dp[0][tr[i]][k-1]+dp[1][i-tr[i]-1][k-1]);
dp[1][i][k]=max(dp[1][i][k],ret);
ret=max(dp[1][tr1][k-1]+dp[0][i-tr1-1][k-1],dp[1][tr[i]][k-1]+dp[0][i-tr[i]-1][k-1]);
dp[1][i][k]=max(dp[1][i][k],ret);
ret=max(dp[0][tr1][k-1]+dp[0][i-tr1-1][k-1],dp[0][tr[i]][k-1]+dp[0][i-tr[i]-1][k-1]);
dp[1][i][k]=max(dp[1][i][k],ret);
if(dp[1][i][k]<0){dp[1][i][k]=-0x3f3f3f3f;}else {dp[1][i][k]+=i;}
}
}
}
for(int i=1;i<=N-10;i++)//处理答案表
{
for(int k=0;k<=17;k++)
{ans[i]=max(ans[i],dp[0][i][k]);ans[i]=max(ans[i],dp[1][i][k]);}
}
while(1)//然后直接查表就行了
{
int t;scanf("%d",&t);if(t!=0)printf("%d\n",ans[t]);else {break;}
}printf("0");return 0;
}
```