Hdu 6769 In Search of Gold —— 上下界优化，树形DP

This way

题意：

现在有一颗大小为n的树，每条边都有两个权值：a,b现在让你最多选k个边的权值为a，其它边的权值为b，使得最终这棵树的直径最短。问你最短是多少。

题解：

最大值最小的问题考虑二分。dp[i][j]表示到第i个点，它的子树中用了j个a的最长长度最短是多少。
然后枚举当前点的选了多少个a的同时枚举子树选了多少个a来进行转移。
但是可以发现这个的时间复杂度是$O(T*N*K^2*log^{2e13})$的，那么很明显就超过了所给的时限。
这个时候用到了一个知识叫做树上背包的上下界优化，也就是说，对于当前点，枚举它已经有的值，然后对于儿子节点，枚举他们的和不超过k的值。虽然看起来这无可厚非，但是实际上最终的复杂度少了一个k。我其实不是很懂，因为在比赛的时候我被A题卡住都还没看过这道题目，但是我还是在这里口胡一下：
假设当前的树是一条链，那么易证这种方法的时间复杂度是$O(NK)$的，因为每个点只会将儿子节点转移到它，所以每个点最多会做k次。然后如果将这条链折了一半，最上面的点的复杂度变成$O(k^2/2)$。但是与此同时，最下面的k个点的总和时间复杂度从$k^2$变成了$1+2+...+k\rightarrow O(k^2/2)$，也就是少了$k^2/2$的时间复杂度（大致）。那么总的时间复杂度看起来还是不变的，那么以此类推…总的时间复杂度为$O(T*N*K*log^{2e13})\rightarrow 10*2e5*20*50$大概就是$2e8$的时间复杂度
事实上我也在经过了一次次尝试之后过了这道题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e4+5;
const ll inf=2e14;
struct node{
    int x;
    ll a,b;
};
vector<node>vec[N];
int n,k;
ll dp[N][25],tmp[25],mid;
int siz[N];
void dfs(int x,int fa){
    for(int i=0;i<=k;i++)
        dp[x][i]=0;
    siz[x]=0;
    for(node ne:vec[x]){
        if(ne.x==fa)continue;
        dfs(ne.x,x);
        for(int i=0;i<=k;i++)tmp[i]=inf;
        for(int i=0;i<=min(siz[x],k);i++){
            for(int j=0;j+i<=k&&j<=siz[ne.x];j++){
                if(dp[x][i]+dp[ne.x][j]+ne.a<=mid)
                    tmp[i+j+1]=min(tmp[i+j+1],max(dp[x][i],dp[ne.x][j]+ne.a));
                if(dp[x][i]+dp[ne.x][j]+ne.b<=mid)
                    tmp[i+j]=min(tmp[i+j],max(dp[x][i],dp[ne.x][j]+ne.b));
            }
        }
        siz[x]+=siz[ne.x]+1;
        for(int i=0;i<=k&&i<=siz[x];i++)
            dp[x][i]=tmp[i];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            vec[i].clear();
        int x,y;
        ll a,b;
        ll l=0,r=0,ans;
        for(int i=1;i<n;i++){
            scanf("%d%d%lld%lld",&x,&y,&a,&b),vec[x].push_back({y,a,b}),vec[y].push_back({x,a,b});
            r+=max(a,b);
        }
        while(r>=l){
            mid=l+r>>1;
            dfs(1,0);
            if(dp[1][k]<=mid)
                r=mid-1,ans=mid;
            else
                l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

本文地址：https://blog.csdn.net/tianyizhicheng/article/details/107598954