思路：題目要求的是減去所有葉子結點的值不超過m時，最長邊的最小值是多少？dp[i][j] 表示j為最長的邊，以i為根節點，減去所有葉子節點的最小總權值。那么我們有2種選擇

1.減去子節點中與葉子節點相連的邊，$dp[i][j]+=dp[v][j]（1<j<(v的權值）$這里我們判斷一下v是不是葉節點如果是葉節點那么權值為inf。

2.減掉與子節點相連的邊，此時子節點減去葉子節點值是大于等于直接減去子節點的值，此時w為v的權值，k為邊權的最大值，那么$dp[i][j]+=min(dp[v][j],w)(w<=j<=k）$

不知道二分咋做

#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> #include<stack> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define SIS std::ios::sync_with_stdio(false) #define space putchar(' ') #define enter putchar('\n') #define lson root<<1 #define rson root<<1|1 typedef pair<int,int> PII; //const int mod=998244353; const int N=2e6+10; const int M=1e3+10; const int inf=0x7f7f7f7f; const int maxx=2e5+7;ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b); }ll lcm(ll a,ll b) {return a*(b/gcd(a,b)); }template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x; } template <class T> void write(T x) {if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10); } ll qsm(int a,int b,int p) {ll res=1%p;while(b){if(b&1) res=res*a%p;a=1ll*a*a%p;b>>=1;}return res; } struct node {int to,nex,w; }edge[M<<1];int head[M<<1]; int tot; int dp[M][M];int a[M]; int k; void add(int u,int v,int w) {edge[++tot].to=v;edge[tot].w=w;edge[tot].nex=head[u];head[u]=tot; } void dfs(int u,int fa) {int flag=0;for(int i=head[u];~i;i=edge[i].nex){int v=edge[i].to,w=edge[i].w;if(v==fa)continue;flag=1;dfs(v,u);for(int j=1;j<w;j++){if(dp[v][j]<inf){dp[u][j]+=dp[v][j];}else{dp[u][j]=inf;//break;}}for(int j=w;j<=k;j++)//子節點最長邊大于等于w直接減掉這個邊{dp[u][j]+=min(w,dp[v][j]);}}if(!flag){for(int i=1;i<=k;i++)dp[u][i]=inf;}} int main() {// SIS;int n,m;memset(head,-1,sizeof head);scanf("%d%d",&n,&m);//int k=0;for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);k=max(k,w);}dfs(1,-1);for(int i=1;i<=k;i++){if(dp[1][i]<=m){printf("%d\n",i);return 0;}}puts("-1");return 0; }

總結

以上是生活随笔為你收集整理的吉吉国王（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。