题解：二分+贪心+树形dp+vector<>回溯时排序（时间复杂度不会爆）
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=1e5+10; LL dp[maxn][2]; LL n,k; vector<LL> G[maxn]; LL w[maxn]; struct node{ LL p1,p2; LL to; }; bool cmp(node x,node y) { return x.p1<y.p1; } LL mx; void dfs(LL u,LL fa,LL mid) { dp[u][1]+=w[u]; dp[u][0]+=1; LL len=G[u].size(); vector<node> t;t.clear(); for(LL i=0;i<len;i++){ LL to=G[u][i]; if(to==fa)continue; dfs(to,u,mid); node pre;pre.p1=dp[to][1];pre.p2=dp[to][0];pre.to=to; t.push_back(pre); } sort(t.begin(),t.end(),cmp); LL pre=w[u]; LL le=t.size(); for(LL j=0;j<le;j++){ if(pre+t[j].p1<=mid){ pre+=t[j].p1; dp[u][0]+=(dp[t[j].to][0]-1); } else{ dp[u][0]+=dp[t[j].to][0]; } } dp[u][1]=pre; mx=max(mx,dp[u][1]); } bool judge(LL x) { for(LL i=1;i<=n;i++){ dp[i][0]=dp[i][1]=0; } mx=0; dfs(1,0,x); if(dp[1][0]<=k&&mx<=x){ return true; } return false; } int main() { int T; scanf("%d",&T); int C=1; while(T--){ scanf("%lld%lld",&n,&k); for(int i=0;i<=n;i++){ G[i].clear(); dp[i][0]=dp[i][1]=0; } LL s,e; for(LL i=1;i<=n-1;i++){ scanf("%lld%lld",&s,&e); G[s].push_back(e);G[e].push_back(s); } for(LL i=1;i<=n;i++){ scanf("%lld",&w[i]); } LL l=1,r=1e15; while(l<=r){ LL mid=(l+r)>>1; if(judge(mid)){ r=mid-1; } else{ l=mid+1; } } printf("Case #%d: %lld\n",C++,l); } return 0; }