写在前面的话
今天考试没有挂分，考场的时候自认为思考得还算投入。希望以后考试的时候对于每一道题目都能有自己深度的思考。
今天考场估分 \(100+80+100+30=310\) , 实际得分 \(100+80+100+30=310,\text{rank2}\) 。
看了一下考试的题解啊，发现自己还是有一些知识点和小 \(\text{trick}\) 不知道的，所以等到 \(\text{CSP-S}\) 之后， \(\text{NOIp}\) 之前小补一下。
今天考场的时候我吸取了之前考试的教训，选择了一个相对合适的开题顺序。我的开题顺序 \(T3-T1-T4-T2\) ，在考后进过仔细评估认为最优开题顺序应该是 \(T1-T3-T4-T2\) 。
\(T1\)
题目描述
现在有一个 \(n\) 节点的数，边有边权。我们定义两点之间的拒了为最短路径上的最小边权。
现在希望给这个树选择一个根，使得根节点到其余节点的距离之和最大，输出这个距离之和。
\(n \leqslant 10^6\) 。
思路点拨
不知道为什么，感觉题面上写满了并查集。我们可以稍稍往这个方面去思考。
考虑一条边在什么时候会成为最大值，我们将全部的边按照边权从大到小排序，再加入并查集的时候我们判断一下边的两边节点的集合，设为 \(S1,S2\) 。如果根在 \(S1\) 里头，那么他到每一个 \(S2\) 的点的距离就是这条边的边权（因为没有加入并查集的边的边权更小），我们给 \(S1\) 的每一个点加上 \(|S2|\times v\) ；同理，每一个在 \(S2\) 的根到达 \(S1\) 的节点的距离都是这条边的边权，所以在 \(S2\) 的点加上 \(|S1|\times v\) 。之后合并两个并查集。
现在我们需要给一些树里的点做加法，还需要合并一些树，难道需要什么科技吗？不需要啊，因为最后每一个节点的点权就是以该节点为根的答案，所以我们的查询是离线的。我们考虑在并查集里头打标记，使用类似于 \(\text{Kruskal}\) 重构树的方式合并+路径压缩。时间复杂度 \(O(n \log n)\) 。
代码实现比较简单，这里不贴了。
\(T2\)
题目描述
对于 \(80 \%\) 的数据，\(n \leqslant 500 , k \leqslant 10\) 。
对于 \(100 \%\) 的数据， \(n \leqslant 500, k \leqslant 60\) 。
思路点拨
考虑我们按照编码一位一位的填。定义状态 \(dp_{l,r}\) 表示区间 \(l,r\) 这个子问题的最小 频率 \(\times\) 码长 。答案要求 \(dp_{1,n}\) 。我们再定义 \(sum_i\) 表示频率的前缀和数组。
因为要求字典序有序，所以我们的目前考虑的区间 \([l,r]\) 的每一个数的编码最低位所形成的序列必须是单调不降的，我们可以将这个区间划分成 \(c(1 <c \leqslant k)\) 段，第 \(i\) 段的最低位就填 \(i\) ,之后就被我们划分成了更小规模的问题，这也符合动态规划的标志。因为要将一个区间划分成若干段，所以我们可以设计一个子序列提取动态规划。
我们定义 \(f_{i,j}\) 表示对于上述区间 \(l,r\) ，我们考虑到下标 \(i\) ,目前是第 \(j\) 段的一个最小贡献。那么转移是比较显然的：
\[f_{i,j}=\min\{f_{mid,j-1}+dp_{mid+1,i}\} \]单轮是 \(O(n^2k)\) ，因为一共有 \(O(n^2)\) 个区间，所以我们考虑对于区间的长度从小到大进行一个转移，时间复杂度 \(O(n^4k)\) 。但是我们注意到，这个 \(f\) 数组的转移十分浪费，因为同一个左端点完全只需要做一遍。所以我们按照左端点从大到小，右端点从小到大的顺序转移，依然可以使得我们在转移 \(dp_{l,r}\) 的时候，\(l<p<q<r\) ，\(dp_{p,q}\) 的函数值已经被计算出来了。所以我们的时间复杂度就优化到了 \(O(n^3k)\) 。因为同一个左端点只需要做一次 \(f\) 数组的动态规划。
之后，我们既然计算出了 \(f\) 数组，\(dp_{l,r}=\max\{f_{r,i}\}+(sum_r-sum_{l-1})\) ，因为我们在区间填了一层编码，所以贡献加上区间和。这个不是时间复杂度的瓶颈，目前可以通过 \(80\) 分。
但是运用计算机强大的计算能力，我们发现 \(dp\) 数组是满足四边形不等式的，所以 \(f\) 数组的计算可以使用决策单调性优化，时间复杂度 \(O(n^2k \log n)\) ，可以通过 \(100\) 分。
代码实现比较简单，不贴了。
标签：test20230914,边权,我们,text,100,节点,dp From： https://www.cnblogs.com/Diavolo/p/17702331.html