题目链接

题解

二分 + 简单的树形dp

我正有练一下dp的必要了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 1005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int h[maxn],ne = 2;struct EDGE{int to,nxt,w;}ed[maxm];inline void build(int u,int v,int w){ ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++; ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++;}int fa[maxn],w[maxn];int n,m,lim;void DFS(int u){ Redge(u) if ((to = ed[k].to) != fa[u]){ fa[to] = u; w[to] = ed[k].w; DFS(to); }}LL f[maxn][2];void dfs(int u){ if (w[u] <= lim) f[u][1] = w[u]; else f[u][1] = INF; f[u][0] = 0; int cnt = 0; Redge(u) if ((to = ed[k].to) != fa[u]){ dfs(to); cnt++; f[u][0] += min(f[to][0],f[to][1]); } if (!cnt) f[u][0] = INF;}bool check(int x){ lim = x; dfs(1); return f[1][0] <= m;}int main(){ while ((n = read()) && (m = read())){ memset(h,0,sizeof(h)); ne = 2; int a,b,w; for (int i = 1; i < n; i++){ a = read(); b = read(); w = read(); build(a,b,w); } DFS(1); int l = 1,r = m,mid; while (l < r){ mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } if (check(l)) printf("%d\n",l); else puts("-1"); } return 0;}