题解：P14633 [2018 KAIST RUN Fall] Utilitarianism
AuCodingFrogHoward
·
·
题解
做题感悟
我的数组怎么被污染了呢（领起下文）
析
先刨去 k 这个限制康康怎么做，结果发现是树上动态规划问题。
下面的折叠框必定破坏你的初次思考。
::::success[转移方程]
搜子树之前，$dp_{u ,0} = 0$，$dp_{u ,1}$ 极大（不合法）。
### 率先转移 $dp_{u ,1}$（照应开头）。
先搜他的儿子 $v$，边权 $w$，往下执行毕，递归浮上来后：$dp_{u ,1} = \max (dp_{u ,1} + \max (dp_{v ,1} ,dp_{v ,0}) ,dp_{u ,0} + dp_{v ,0} + w)$。
是已或未连接儿子 $v$ 的转移。
### 转移 $dp_{u ,0}$。
先搜他的儿子 $v$，往下执行毕，递归浮上来后：$dp_{u ,0} = dp_{u,0} + \max (dp_{v ,1} ,dp_{v ,0})$。
没有制约不多解释。
::::
### 王钦石分治优化
王钦石分治优化。
证明凸性。
考虑给每条边加一个权 $dlt$。
设 $f(x)$ 为 $dlt = x$ 时的最优解。
考虑证明 $f(i - 1) - f(i - 2) \ge f(i) - f(i - 1)$。
选择的策略可以按结局分为两段：饱和（加不了了）、不饱和（能加不优）**这只是因为 $dlt$ 过小**。
讨。
::::info[甲：$i$，$i - 1$，$i - 2$ 均饱和]
发现选的边数一致，设为 $k$。
不等式取等，两边皆为 $k$。
得证。
::::
::::info[乙：仅 $i - 2$ 不饱和]
在 $i - 2$ 意义下强行选 $i - 1$ 增边，发现不优，同甲。
具体的，左边需要加上一些负值方可等于甲。
得证。
::::
::::info[丙：仅 $i$ 饱和]
:::info[一：$i - 2$ 到 $i - 1$ 增边]
全选增边证。
得证。
:::
:::info[二：$i - 2$ 到 $i - 1$ 不增边]
同乙。
得证。
:::
子情况皆真。
得证。
::::
::::info[丁：$i$，$i - 1$，$i - 2$ 均不饱和]
同丙的策略证。
得证。
::::
## 码
别忘了有斜率平台。
::::info[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 250005
#define endl "\n"
#define nullptr 0
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);
using namespace std;
int n ,k ,ans;
struct vnode
{
int v ,w;
};
vector <vnode> vec[maxn];
void adde (int u ,int v ,int w)
{
vec[u].push_back ({v ,w});
vec[v].push_back ({u ,w});
}
struct fnode
{
int mxm ,cnt;
friend bool operator < (fnode a ,fnode b)
{
if (a.mxm < b.mxm)
return 1;
if (a.mxm > b.mxm)
return 0;
if (a.cnt < b.cnt)
return 1;
return 0;
}
friend fnode operator + (fnode a ,fnode b)
{
fnode c = {a.mxm + b.mxm ,a.cnt + b.cnt};
return c;
}
}dp[maxn][2];//dp_{i ,j} = 以 i 为根，向子边选过（吗）？
void DFS (int u ,int fa ,int dlt)
{
dp[u][0] = {0 ,0} ,dp[u][1] = {- INT_MAX ,0};
for (int i = 0 ;i < vec[u].size () ;i ++)
{
int v = vec[u][i].v ,w = vec[u][i].w + dlt;
if (v == fa)
continue ;
DFS (v ,u ,dlt);
dp[u][1] = max (dp[u][0] + dp[v][0] + (fnode){w ,1} ,dp[u][1] + max (dp[v][0] ,dp[v][1]));
dp[u][0] = dp[u][0] + max (dp[v][0] ,dp[v][1]);
}
return ;
}
bool check (int mid)
{
DFS (1 ,- 1 ,mid);
fnode zc = max (dp[1][0] ,dp[1][1]);
ans = zc.mxm;
return (zc.cnt >= k);
}
signed main()
{
I AK CSP
cin >> n >> k;
for (int i = 1 ;i < n ;i ++)
{
int u ,v ,w;
cin >> u >> v >> w;
adde (u ,v ,w);
}
int L = -1e12 ,R = 1e12 ,Z ,res = 1e16;
while (L <= R)
{
Z = (L + R) >> 1;
if (check (Z))
res = Z ,R = Z - 1;
else
L = Z + 1;
}
check (res);
if (res >= 1e13)
{
cout << "Impossible" << endl;
return 0;
}
cout << ans - k * res << endl;
return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.
```
::::