【三校联考10.24】点亮

本文主要是介绍【三校联考10.24】点亮，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

@问题描述@

间宫卓司种下一个小树苗，它长成了一棵 n 个点的有根树，根节点为 1，点 u 的父节点为 $p_u$。由于在生长过程中没有加以人工干预，所以这棵树的形态有一定的随机性：保证 $p_u$ 是在 1 到 u − 1 中等概率随机选取的。现在，这棵树的所有节点都黯淡无光。他要使用救世主的法力来点亮一些点，使这棵树变得更加美丽。
对于有序点对 (u, v)（u≠v），如果 u 没有被点亮且以 lca(u, v) 为根的子树中没有被点亮的点数大于被点亮的点数，那么会贡献 $a[u][v]$ 的美丽度；如果 u 被点亮，且以 lca(u, v) 为根的子树中被点亮的点数大于等于没有被点亮的点数，则会贡献 $b[u][v]$ 的美丽度；否则不贡献美丽度。贡献的美丽度可以为负数。
间宫卓司想知道，通过点亮一些点，能得到整棵树的美丽度最大是多少。

输入
第一行，一个正整数 n。
第二行，n − 1 个正整数 $p_2,p_3,...,p_n$。保证 $p_u$ 是在 1 到 u − 1 中等概率随机选取的。
接下来 n 行，第 u 行有 2(n−1) 个数，分别为 $a[u][1],b[u][1],...,a[u][u-1],b[u][u-1],a[u][u+1],b[u][u+1],...,a[u][n],b[u][n]$（即去掉 v = u 后的 n − 1对）。

输出
一个整数表示能得到整棵树的美丽度的最大值。

样例输入1
2
1
-71 69
100 -47
样例输出1
69
解释：最优方案是点亮 1 不点亮 2，此时 (1, 2) 的贡献为 69，(2, 1) 没有贡献。

样例输入2
3
1 1
-32 19 84 21
-20 0 7 -86
-37 -33 16 -66
样例输出2
39
3.4.3
解释：最优方案是不点亮 1, 2，点亮 3。

数据限制
对于 40% 的数据，$1\le n\le 16$。
对于 80% 的数据，$1\le n\le 200$。
对于 100% 的数据，$1\le n\le 1000，-100\le a[u][v],b[u][v]\le 100$，保证 $p_u$是在 $1$ 到 $u-1$ 中等概率随机选取的。

@分析1 - 随机的性质@

【题解中提到：“众所周知，按此方法随机得到的树有几个常用性质：……”】
【恩我为啥什么都不知道？？？】

好的……既然题目中多次强调树是随机生成的，那么这一定是有用的。在这道题，随机树有以下性质可供我们使用：
1）点 i 的期望深度为 1/1 + 1/2 + 1/3＋ … + 1/i ≈ ln i
2）以点 i 为根的子树期望大小 $\le$ n/i
【其实这种树上每个节点的期望度数也是log级别的……只是这道题没有用到。】

这几个性质怎么证明呢？如果是大佬当然可以直接用数学方法推导或者用期望 dp 快速秒掉。但其实可以写一个生成随机树的程序，多刷几组验证一下，大概是那个数量级就OK。（hhhh我真是机智）

但是……emmm深度还好说，谁知道会根据子树大小来设计算法啊……

@分析2 - 利用性质@

为方便表述，如果以 i 为根的子树点亮的点多，我们称它为白点；否则为黑点。

我们对于每一个节点，计算它对答案的贡献。但是这个算法的关键点是，我们不知道它祖先的颜色，自上而下的算法不太适用。

这个时候应该将思维暴力一点：既然每个点的期望深度是log级别的，那我们不妨就设计一个以深度为底数的指数级算法来求解。深度是log级别的等价于每个点只会有log个祖先，于是就和上面的讨论有关联了：我们可以二进制枚举每个节点祖先的颜色，计算该节点的贡献，进行状压dp。

还没完。我们要判断一个子树是不是真的是白色的，不能你说它是白色的它就是白色的对吧。所以我们要将这颗子树内被点亮的点数存入状态进行转移。眼看着这个时间复杂度飙升，于是第二个性质就有用了：因为期望深度n/i，根据一些玄学的时间复杂度证明，它的时间复杂度竟然还是稳定在O(n^2)的。

具体细节请往下翻。

@算法细节@

定义$dp[i][j][s]$表示以 i 为根的子树有 j 个被点亮的点，且从 i 到根的路径上点的黑白状态为 s 时的最大答案值。
定义$f[0/1][i][s]$表示当 i 被点亮/没有被点亮，且从 i 到根的路径上点的黑白状态为 s 时 i 对答案的贡献。
定义$g[0/1][i][j]$表示当 i 被点亮/没有被点亮时，所有满足lca(i, k) = (i的第 j 个祖先)的k，$a[i][k]/b[i][k]$之和。

$g$ 数组可以靠枚举节点+计算lca在O(n^2log n)的时间内求解出来。
利用 $g$ 可以在O(n*2^logn) = O(n^2)的时间内求解 $f$。
转移 $dp[i][j][s]$ 时可以以 j 为容量做树上背包。初始状态为$dp[0/1][i][0/1]=f[0/1][i][s]$。

以 i 为根时，树上背包的时间复杂度O(siz[i]²)，状态有O(2^dep[i])个。总时间复杂度$O({\sum }_{i=1}^{i\le n}siz[i{]}^2\ast 2^{dep[i]})=O(n^2\ast \log n)$
至于为什么可以参考下面的证明。

强烈建议看一下代码的实现细节，不然可能写得很丑。

@代码@

虽然大致思路是这样的，但是还是有一些细节必须提一提：
1）dp数组如果真的那么定义，虽然时间没问题，但空间会爆炸……正确做法是将状态 s 作为一个dfs的参数传递下去。因为一个状态 s 对于它的父节点只会产生一次贡献，用过一次过后就可以直接覆盖掉了。
2）不是0/1背包或者完全背包，所以要滚动数组……
3）f数组要用vector，比着子树大小开，不然也会爆空间……
4）因为一个点作为白点和作为黑点两种情况时它们子树中含有的点亮的点的个数不一样，可以先统一将它们存入某一数组h，再进行背包。
5）记得删除不合法的状态值。
6）事实上求解深度和子树大小不需要dfs，因为它的父亲节点编号一定小于它，所以可以用递推来进行求解。
7）求lca也不需要倍增。因为每个节点的期望深度是log级别的……就直接暴力好了。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = (1<<30);
const int MAXN = 1000;
struct edge{int to;edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v) {edge *p = (++ecnt);p->to = v, p->nxt = adj[u], adj[u] = p;
}
int dep[MAXN + 5], siz[MAXN + 5];
int fa[MAXN + 5], a[2][MAXN + 5][MAXN + 5];
int dp[2][MAXN + 5][MAXN + 5], g[2][MAXN + 5][30], h[MAXN + 5][MAXN + 5];
vector<int>f[2][MAXN + 5];
void Copy(int x) {for(int i=0;i<=siz[x];i++)dp[0][x][i] = dp[1][x][i];
}
void Init1(int x) {for(int i=0;i<=siz[x];i++)dp[1][x][i] = -INF;
}
void Init2(int x) {for(int i=0;i<=siz[x];i++)h[x][i] = -INF;
}
void dfs(int rt, int s) {Init1(rt); dp[1][rt][0] = f[0][rt][s];dp[1][rt][1] = f[1][rt][s];Copy(rt);int tot = 1;for(edge *p=adj[rt];p!=NULL;p=p->nxt) {Init1(rt); Init2(p->to);dfs(p->to, s<<1); dfs(p->to, s<<1|1);tot += siz[p->to];for(int i=0;i<=siz[p->to];i++)for(int j=i;j<=tot;j++)dp[1][rt][j] = max(dp[1][rt][j], dp[0][rt][j-i] + h[p->to][i]);Copy(rt);}if( s&1 ) {for(int i=(siz[rt]+1)/2;i<=siz[rt];i++)h[rt][i] = dp[0][rt][i];}else {for(int i=0;i<(siz[rt]+1)/2;i++)h[rt][i] = dp[0][rt][i];}
}
int main() {freopen("light.in", "r", stdin);freopen("light.out", "w", stdout);int n;scanf("%d", &n);for(int i=2;i<=n;i++) {scanf("%d", &fa[i]);addedge(fa[i], i);}for(int i=1;i<=n;i++) {dep[i] = dep[fa[i]] + 1;siz[i] = 1;}for(int i=n;i>=1;i--)siz[fa[i]] += siz[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) {if( i == j ) continue;scanf("%d%d", &a[0][i][j], &a[1][i][j]);int p = i, q = j, r = 0;while( dep[p] > dep[q] ) p = fa[p], r++;while( dep[q] > dep[p] ) q = fa[q];while( p != q ) p = fa[p], q = fa[q], r++;g[0][i][r] += a[0][i][j];g[1][i][r] += a[1][i][j];}for(int i=1;i<=n;i++) {int t = 1<<dep[i];for(int s=0;s<t;s++) {f[0][i].push_back(0);f[1][i].push_back(0);int p = i;for(int j=0;j<dep[i];j++,p=fa[p]) {int c = ((1<<j)&s) ? 1 : 0;f[c][i][s] += g[c][i][j];}}}int ans = -INF;dfs(1, 0); dfs(1, 1);for(int i=0;i<=siz[1];i++) {ans = max(ans, h[1][i]);
//		printf("%d\n", h[1][i]);}printf("%d\n", ans);
}

@证明（过于枯燥）@

首先使用归纳法证明期望深度，记$d_u$为u的期望深度。边界情况$d_1=1$。
假设已知$d_{u-1}=1/1+1/2+...1/(u-2)+1$
则：$d_u=1+\frac{{\sum }_{i=1}^{i<u}{d}_i}{u-1}$，$d_{u-1}=1+\frac{{\sum }_{i=1}^{i<u-1}{d}_i}{u-2}$
去分母：$(u-1)d_u=u-1+{\sum }_{i=1}^{i<u}{d}_i$，$(u-2)d_{u-1}=u-2+{\sum }_{i=1}^{i<u-1}{d}_i$
两式相减：$(u-1)d_u-(u-2)d_{u-1}=1+d_{u-1}$
移项：$(u-1)d_u-(u-1)d_{u-1}=(u-1)(d_u-d_{u-1})=1$
所以：$d_u-d_{u-1}=1/(u-1)$，$d_u=1/1+1/2+...+1/(u-1)+1$
得证。

一样使用归纳法证明期望子树大小，记$s_u$为u的期望子树大小。边界情况$s_n=1$。
假设已知$s_{u+1}=\frac{n}{u+1}$
则：$s_u=1+{\sum }_{i=u+1}^{i\le n}\frac{s_i}{i-1}$，$s_{u+1}=1+{\sum }_{i=u+2}^{i\le n}\frac{s_i}{i-1}$
两式相减：$s_u-s_{u+1}=\frac{s_{u+1}}{u}$，$s_u=\frac{u+1}{u}\ast s_{u+1}=\frac{n}{u}$
得证。

再来证明时间复杂度：
$$\begin{gathered} O({\sum }_{i=1}^{i\le n}siz[i{]}^2\ast 2^{dep[i]})=O({\sum }_{i=1}^{i\le n}(n/i{)}^2\ast 2^{\log i}) \\ =O({\sum }_{i=1}^{i\le n}(n/i{)}^2\ast i)=O({\sum }_{i=1}^{i\le n}{n}^2/i)=O(n^2\ast {\sum }_{i=1}^{i\le n}1/i) \\ =O(n^2\log n) \end{gathered}$$

……
我可以假装我没学过数学吗？

@END@

就是这样，新的一天里，也请多多关照哦(ノω<。)ノ))☆.。

这篇关于【三校联考10.24】点亮的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---