HDU多校第二场 1007 In Search of Gold —— 二分 + 树形dp

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个点的树，每条边有两个权值 $a$ 和 $b$
    要求恰好选择 $k$ 条边使其权值为 $a$，其他的边权值为 $b$
    求最小直径

解题思路：

    容易想到树形 $dp$
    $dp[i][j]$ 为以 $i$ 为根的子树，选择了 $j$ 条边时，到叶子的最远距离
    但是这样不能维护出最小直径

    观察其实答案满足二分性质，那么二分一个 $mid$
    在上面的 $dp$ 转移过程中，若子树 $v$ 向父亲 $u$ 更新
    则 $u$ 能形成的最大直径为 $dp[u][i]+dp[v][j]+a$ 或者为 $dp[u][i]+dp[v][j]+b$
    只有当这个最大直径 $\le mid$ 时，才能进行转移，否则非法
    因此只需要二分转移时的界限，最后看 $dp[1][k]$ 是否同时满足 $\le mid$ 即可
    同时注意转移时，第二维的上限为 $min(边数，k)$，而不是子树大小
    时间复杂度：$O(nklogn)$

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 4e4 + 5;
int T, n, k, sz[maxn];
ll dp[maxn][25], t[25];
struct node {int v, a, b;
} ;
vector <node> g[maxn];void dfs(int u, int fa, ll x) {sz[u] = 0; dp[u][0] = 0;for(auto to : g[u]) {int v = to.v, a = to.a, b = to.b;if(v == fa) continue;dfs(v, u, x);int now = min(sz[u] + sz[v] + 1, k);for(rint i=0; i<=now; ++i) t[i] = 2e15;for(rint i=0; i<=sz[u]; ++i)for(rint j=0; j<=sz[v]&&i+j<=k; ++j) {if(dp[u][i] + dp[v][j] + a <= x)t[i+j+1] = min(t[i+j+1], max(dp[u][i], dp[v][j] + a));if(dp[u][i] + dp[v][j] + b <= x)t[i+j] = min(t[i+j], max(dp[u][i], dp[v][j] + b));}sz[u] = now;for(rint i=0; i<=now; ++i) dp[u][i] = t[i];}
}signed main() {scanf("%d", &T);while(T--) {ll l = 0, r = 0, mid;scanf("%d%d", &n, &k);for(rint i=1; i<=n; ++i) g[i].clear();for(rint i=1, u, v, a, b; i<n; ++i) {scanf("%d%d%d%d", &u, &v, &a, &b);g[u].push_back({v, a, b});g[v].push_back({u, a, b});r += max(a, b);}while(l <= r) {mid = l + r >> 1;dfs(1, 0, mid);if(dp[1][k] <= mid) r = mid - 1;else l = mid + 1;}printf("%lld\n", l);}
}