https://vjudge.net/problem/UVA-1267
题意：
有一棵树，上面有一个放着水源的点s，给出一个数k，这个水源可以覆盖路径长度到s不超过k的叶子节点。现在需要把所有的叶子节点都用水源覆盖，问至少需要再放置多少个水源。
思路：
首先，这种树的问题并且明显提供了一个特殊点的题，我们可以把无根树转化为有根树简化需要解决的问题。
这题，经过转化之后，所有的深度小于等于k的节点，我们都不考虑了，只考虑深度大于k的叶子节点。
在无根树转化为有根树的过程中，把所有的深度大于k的叶子节点用一个深度对应的数组存起来。
之后，我们从最深的深度开始枚举，这个深度的如果有叶子节点并且没有被覆盖的话，那么我们就找到这个节点的第k级父亲（直接父亲是第一级），从这个祖先节点开始一次dfs，标记深度不超过k的所有节点。
解释：
从最深的深度开始枚举，并且找到它的第k级父亲这个操作，可以保证我们加的水源是最少的，假设k为4，如果用它的第3级父亲开始dfs，那么如果第4级父亲还有其它叶子节点，就没有被覆盖，但是我们在第四级父亲，既可以把这个深度的所有节点都覆盖，并且可以把第四级父亲之下的所有的叶子节点都覆盖，那么说明父亲的级别越高，那么可能覆盖的点就会越多，那么当前的点的第k级父亲就是可以覆盖到这个点的级别最高的父亲。
注意：
在dfs中，建图是建的双向图，所以一定要判断下一个dfs的点是不是与父亲节点相等。Debug了很久。。。
代码：
?1 #include <stdio.h> ?2 #include <string.h> ?3 #include <vector> ?4 using namespace std; ?5 ??6 vector<int> g[1005],node[1005]; ?7 int n,s,k; ?8 bool cover[10005]; ?9 int fa[1005]; 10 ?11 void dfs(int pre,int cur,int dep) 12 { 13 ????//printf("*\n"); 14 ?15 ????fa[cur] = pre; 16 ?17 ????if (g[cur].size() == 1 && dep > k) node[dep].push_back(cur); 18 ?19 ????for (int i = 0;i < g[cur].size();i++) 20 ????{ 21 ????????int to = g[cur][i]; 22 ?23 ????????if (to != pre) dfs(cur,to,dep + 1); 24 ????} 25 } 26 ?27 void dfs2(int v,int d) 28 { 29 ????//printf("**\n"); 30 ?31 ????cover[v] = 1; 32 ?33 ????for (int i = 0;i < g[v].size();i++) 34 ????{ 35 ????????int to = g[v][i]; 36 ?37 ????????if (to != v && d < k) dfs2(to,d+1); 38 ????} 39 } 40 ?41 int solve(void) 42 { 43 ????memset(cover,0,sizeof(cover)); 44 ?45 ????int ans = 0; 46 ?47 ????for (int d = n - 1;d > k;d--) 48 ????{ 49 ????????for (int i = 0;i < node[d].size();i++) 50 ????????{ 51 ????????????int x = node[d][i]; 52 ?53 ????????????//printf("%d ** \n",x); 54 ?55 ????????????if (cover[x]) continue; 56 ?57 ????????????//printf("0000\n"); 58 ?59 ????????????for (int j = 0;j < k;j++) x = fa[x]; 60 ?61 ????????????dfs2(x,0); 62 ?63 ????????????ans++; 64 ????????} 65 ????} 66 ?67 ????return ans; 68 } 69 ?70 int main() 71 { 72 ????int t; 73 ?74 ????scanf("%d",&t); 75 ?76 ????while (t--) 77 ????{ 78 ????????scanf("%d",&n); 79 ?80 ????????scanf("%d%d",&s,&k); 81 ?82 ????????for (int i = 0;i <= n;i++) ?83 ????????{ 84 ????????????node[i].clear(); 85 ????????????g[i].clear(); 86 ????????} 87 ?88 ????????for (int i = 0;i < n - 1;i++) 89 ????????{ 90 ????????????int x,y; 91 ?92 ????????????scanf("%d%d",&x,&y); 93 ?94 ????????????g[x].push_back(y); 95 ????????????g[y].push_back(x); 96 ????????} 97 ?98 ????????dfs(-1,s,0); 99 100 ????????printf("%d\n",solve());101 ????}102 103 ????return 0;104 }uva1267 Network
原文地址：http://www.cnblogs.com/kickit/p/7615706.html