当前位置: 代码迷 >> 综合 >> HDU多校第二场 1007 In Search of Gold —— 二分 + 树形dp
  详细解决方案

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

热度:42   发布时间:2024-01-09 10:39:51.0

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

题目大意:

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

解题思路:

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

    观察其实答案满足二分性质,那么二分一个 m i d mid mid
    在上面的 d p dp dp 转移过程中,若子树 v v v 向父亲 u u u 更新
    则 u u u 能形成的最大直径为 d p [ u ] [ i ] + d p [ v ] [ j ] + a dp[u][i] + dp[v][j] + a dp[u][i]+dp[v][j]+a 或者为 d p [ u ] [ i ] + d p [ v ] [ j ] + b dp[u][i] + dp[v][j] + b dp[u][i]+dp[v][j]+b
    只有当这个最大直径 ≤ m i d ≤mid mid 时,才能进行转移,否则非法
    因此只需要二分转移时的界限,最后看 d p [ 1 ] [ k ] dp[1][k] dp[1][k] 是否同时满足 ≤ m i d ≤mid mid 即可
    同时注意转移时,第二维的上限为 m i n ( 边 数 , k ) min(边数,k) min(k),而不是子树大小
    时间复杂度: O ( n k l o g n ) O(nklogn) 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);}
}
  相关解决方案