HDU多校第五场--1007/6820 TREE（简单树形dp

题意：http://acm.hdu.edu.cn/showproblem.php?pid=6820

题目要求一个最大子图（顶点度数超过k的点数最多只有一个）

思路：

注意k=1的时候，dp保留每个点选k-1个，和全选的状态，再记录一些类似最大值最小的临界值（换根判断有没有选儿子用）

稍微有点小绕，写仔细点就行

  1 struct EDGE
  2 {
  3     int to,next,cost;
  4 }edge[N<<1];
  5 int etot;
  6 int head[N];
  7 void Init(int n)
  8 {
  9     etot=0;
 10     for(int i=0;i<=n;++i)
 11         head[i]=0;
 12 }
 13 void add(int from,int to,int cost)
 14 {
 15     ++etot;
 16     edge[etot].to=to;
 17     edge[etot].cost=cost;
 18     edge[etot].next=head[from];
 19     head[from]=etot;
 20 }//for(int i=head[u];i;i=edge[i].next)
 21 
 22 
 23 int n,k;
 24 int val[N][3],lvl[N],up[N],min_[N];
 25 vector<vector<int> >G(N);
 26 void dfs(int u,int f)
 27 {
 28     for(int i=head[u];i;i=edge[i].next)
 29     {
 30         int to=edge[i].to;
 31         if(to==f)continue;
 32         dfs(to,u);
 33         G[u].push_back(edge[i].cost+val[to][0]);
 34     }
 35     int sz=G[u].size();
 36     if(sz==0)return;
 37     sort(G[u].begin(),G[u].end());
 38     for(int i=sz-1;i>=0;--i)
 39     {
 40         int v=G[u][i];
 41         if(sz-i<k)val[u][0]+=v,min_[u]=v;
 42         if(sz-i==k)lvl[u]=v;
 43         if(sz-i<=k)val[u][1]+=v;
 44         val[u][2]+=v;
 45     }
 46 }
 47 
 48 int ans;
 49 void dfs2(int u,int f)
 50 {
 51     ans=max(ans,val[u][2]+up[u]);
 52     for(int i=head[u];i;i=edge[i].next)
 53     {
 54         int to=edge[i].to;
 55         if(to==f)continue;
 56         int v;
 57         if(val[to][0]+edge[i].cost>lvl[u])
 58             v=val[u][0]-val[to][0]+(k==1?0:max(lvl[u],up[u]));
 59         else
 60         {
 61             if(min_[u]<up[u])
 62                 v=val[u][0]-min_[u]+(k==1?0:up[u]);
 63             else
 64                 v=val[u][0];
 65             v+=edge[i].cost;
 66         }
 67         up[to]=v;
 68         dfs2(to,u);
 69     }
 70 }
 71 
 72 void solve()
 73 {
 74     sc("%lld%lld",&n,&k);
 75     ans=0;
 76     Init(n);
 77     for(int i=0;i<=n;++i)min_[i]=up[i]=lvl[i]=val[i][0]=val[i][1]=val[i][2]=0;
 78     for(int i=1;i<n;++i)
 79     {
 80         int u,v,w;
 81         sc("%lld%lld%lld",&u,&v,&w);
 82         add(u,v,w);
 83         add(v,u,w);
 84     }
 85     dfs(1,0);
 86     dfs2(1,0);
 87     for(int i=0;i<=n;++i)G[i].clear();
 88     if(k==0)ans=0;
 89     pr("%lld
",ans);
 90 }
 91 
 92 signed main()
 93 {
 94     int T;
 95     sc("%lld",&T);
 96     while(T--)solve();
 97     return 0;
 98 }
 99 
100 /**************************************************************************************/