11.7 模拟赛题解

标签：dep 题解 11.7 ydep mxd y2 节点 模拟

幸终

简要题意

给定一棵树，\(1\) 号节点为根节点，记 \(d_i\) 为 \(i\) 号节点到根节点最短路径所经过的边数，\(mxd=max_{i=1}^nd_i\) 。现在要把这棵树剖分成若干条链，每条链链底结点记为 \(y\) ，链上的结点记为 \(u\) ，那么每条链的代价为 \(-h_y+\sum_{u}(C_y\cdot (mxd-d_u)+C_y^2)\) ，求将整棵树剖分完的最小代价。

简要题解

式子转化

首先题目所给的那个 \(mxd-d_i\) 有点麻烦，我们把它扬了记 \(dep_i=mxd-d_i\) 。

对于每条链，我们记链顶为 \(x\) ，链底为 \(y\) ，可以发现这条链的代价可以稍微转化一下，变为一个只与 \(x,y\) 有关的函数。

\[-h_y+(dep_x-dep_y+1)C_y^2+C_y\frac{(dep_x-dep_y+1)(dep_x+dep_y)}{2} \]

\[\frac{1}{2}\left [ C_ydep_x^2+(2C_y^2+C_y)dep_x-2dep_yC_y^2+2C_y^2-C_ydep_y^2+C_ydep_y-2h_y \right ] \]

我们将其看作一个二次函数。

$a=C_y,b=2,C_y^{2+C_y,c=-2dep_yC_y}2+2C_y^2-C_ydep_y2+C_ydep_y-2h_y $ 。

显然有 \(a>0 ,b>0\) ，则该二次函数的对称轴在 \(y\) 轴右侧，

\[\]

标签：dep,题解,11.7,ydep,mxd,y2,节点,模拟
From： https://www.cnblogs.com/oscaryangzj/p/16874986.html