具体讲解和证明，黑书上有，IOI2004国家集训队论文--王汀 中也有讲解， 这里简单介绍求法过程。
为了方便叙述，把顶点V0的度数<=K称作度限制条件，把满足这一条件的生成树称为度限制生成树，把权值和最小的度限制生成树称为最小度限制生成树。
要求的最小K度生成树，应该有以下的步骤：
算法框架：
1. 先求出最小m度限制生成树；
2. 由最小m度限制生成树得到最小m+1度限制生成树;
3. 当dT(v0)=k时停止(即当V0的度为k的时候停止)；
部分引用论文：
第一步求解最小m度限制生成树：原图中去掉和V0相连的所有边，得到m个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中dT(v0)≥m。也就是说，当k<m时，问题无解。对每个连通分量求一次最小生成树，对于每个连通分量V’，求一点v1，v1∈V',且ω(v0,v1)=min{ω(v0,v')|v'∈V'}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。
第二步，由最小m度限制生成树，得到最小m+1度限制生成树，对于和V0相邻的点v，则可以知道一定会有一个环出现，只要找到这个环上的最大权边，用边(V0, v)替换掉，就可以得到一个m+1度限制生成树，枚举所有和V0相邻点v，找到替换后增加权值最小的一次替换，就可以求得m+1度限制生成树。。如果每添加一条边，都需要对环上的边一一枚
举，时间复杂度将比较高，这里，动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),ω(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞| (v0,v’)∈E(T)。
第三步, 当度为K的时候就可以退出了。
pku1639 Picnic Planning 野餐计划
这里就是一个度限制生成树的应用，聚集地点最多能放K辆轿车，把聚集地点park 作为度限制点，就可以求所有小于等于K的度限制生成树，取他们中最小值，即为这题的解。
附上一份代码，写的比较乱，仅供参考。
1 #include<stdio.h> 2 #include<string.h> 3 #define NN 30 4 #define INF 0x3fffffff 5 int idx, S;// S为需要限制度的那一点 6 int k, mst;// k表示k度限制，mst为最后的结果 7 int pre[NN]; 8 int mark[NN]; 9 int dis[NN]; 10 int vis[NN]; 11 char str[NN][NN]; 12 int map[NN][NN]; 13 int best[NN]; // 存的是最大权值边的终点 14 int edg[NN][NN];// edg[i][j] = 1 表示边[i,j]已在生成树中 15 int father[NN];// 生成树中的父节点 16 17 int find(char s[]){ 18 int i; 19 for (i = 0; i < idx; i++){ 20 if (strcmp(str[i], s) == 0) return i; 21 } 22 return -1; 23 } 24 25 void dfs(int cur){// 将树拉成有根树 26 int i; 27 for (i = 0; i < idx; i++){ 28 if (edg[i][cur] && mark[i]){ 29 father[i] = cur; 30 mark[i] = 0; 31 dfs(i); 32 } 33 } 34 } 35 36 int prim(int s){// 求最小生成树 37 int i, key, Min; 38 int sum = 0; 39 memset(pre, 0, sizeof(pre)); 40 for (i = 0; i < idx; i++){ 41 dis[i] = map[s][i]; 42 pre[i] = s; 43 } 44 memset(mark, 0, sizeof(mark)); 45 mark[s] = 1; 46 vis[s] = 1; 47 48 while(1){ 49 Min = INF; 50 key = -1; 51 for (i = 0; i < idx; i++){ 52 if (!vis[i] && !mark[i] && dis[i] < Min){ 53 key = i; 54 Min = dis[i]; 55 } 56 } 57 if (key == -1) break; 58 mark[key] = 1; 59 vis[key] = 1; 60 edg[pre[key]][key] = edg[key][pre[key]] = 1; 61 sum += dis[key]; 62 for (i = 0; i < idx; i++){ 63 if (!vis[i] && !mark[i] && dis[i] > map[key][i]){ 64 dis[i] = map[key][i]; 65 pre[i] = key; 66 } 67 } 68 } 69 Min = INF; 70 int root = -1; // 树根 71 for (i = 0; i < idx; i++){ 72 if (mark[i] && map[i][S] < Min){ 73 Min = map[i][S]; 74 root = i; 75 } 76 } 77 // 拉成有根树 78 mark[root] = 0; 79 dfs(root); 80 father[root] = S; 81 return sum + Min; 82 } 83 84 int Best(int x){// 求得x到S路径上的最大权值边 85 int tmp; 86 if (father[x] == S) return -1; 87 if (best[x] != -1){ 88 return best[x]; 89 } 90 tmp = Best(father[x]); 91 if (tmp != -1 && map[tmp][father[tmp]] > map[father[x]][x]){ 92 best[x] = tmp; 93 }else best[x] = x; 94 return best[x]; 95 } 96 97 void Solve() 98 { 99 int i, j; 100 memset(vis, 0, sizeof(vis)); 101 vis[S] = 1; 102 int m = 0;// 分支个数 103 mst = 0;// 最小生成树和 104 memset(father, -1, sizeof(father)); 105 memset(edg, 0, sizeof(edg)); 106 for (i = 0; i < idx; i++){// 先求得m限制生成树 107 if (!vis[i]){ 108 m++; 109 mst += prim(i); 110 } 111 } 112 /* for (i = 0; i < idx; i++){ 113 printf("%d----%d %d\n", father[i], i, map[i][father[i]]); 114 }可以用于调试错误 115 */ 116 int minadd, ax, bx,tmp; 117 int change; // 回路上权值最大的边，用于交换 118 for (i = m + 1; i <= k && i < idx; i++){ 119 // 再由m度生成树得到m+1度生成树，最后求得k限制生成树 120 memset(best, -1, sizeof(best)); 121 for (j = 0; j < idx; j++){ 122 if (best[j] == -1 && father[j] != S){ 123 Best(j); 124 } 125 } 126 minadd = INF; // 交换边的最小差值 127 for (j = 0; j < idx; j++){// 遍历所有临边 128 if (map[S][j] != INF && father[j] != S){ 129 ax = best[j]; 130 bx = father[ax]; 131 tmp = map[S][j] - map[ax][bx]; 132 if (tmp < minadd){ 133 minadd = tmp; 134 change = j; 135 } 136 } 137 } 138 if (minadd >= 0) break;//用于度数不大于k的限制，如果k限制，就不用break了 139 mst += minadd; 140 ax = best[change]; 141 bx = father[ax]; 142 map[ax][bx] = map[bx][ax] = INF; 143 father[ax] = bx = S;// 改变生成树，将点ax直接指向源点S 144 map[ax][bx] = map[bx][ax] = map[change][S]; 145 map[S][change] = map[change][S] = INF; 146 } 147 } 148 int main() 149 { 150 int i, j, n, x, y, d; 151 char s1[NN], s2[NN]; 152 scanf("%d", &n); 153 for (i = 0; i <= NN - 2; i++){ 154 for (j = 0; j <= NN - 2; j++){ 155 map[i][j] = INF; 156 } 157 } 158 idx = 1; 159 strcpy(str[0], "Park"); 160 while(n--){ 161 scanf("%s%s%d", s1, s2, &d); 162 x = find(s1); 163 if (x == -1){ 164 strcpy(str[idx++], s1); 165 x = idx - 1; 166 } 167 y = find(s2); 168 if (y == -1){ 169 strcpy(str[idx++], s2); 170 y = idx - 1; 171 } 172 if (d < map[x][y]){ 173 map[x][y] = d; 174 map[y][x] = d; 175 } 176 } 177 scanf("%d", &k); 178 S = 0; 179 Solve(); 180 printf("Total miles driven: %d\n", mst); 181 return 0; 182 } 183