题意:给出t组数据，每组给出n个点，original server s(根)，到达s的最大路径不超过k，求满足叶子结点到server的路径不超过k需要增加的server个数。
知识点大概是……贪心+无根树→有根树，首先把无根树转化为以s为根的树（dfs建树），然后按深度将节点放到邻接表里，一层一层从叶子结点向根的方向遍历，每向上搜索k级还未找到server，ans+1，
并更新节点访问情况。
emmmmmm……图的知识点都还没开始学的感觉，这里先记笔记记笔记，码下邻接表对树的实现方法和dfs建树不啦不啦啥的。
#include<iostream> ??//greedy 自叶子向上遍历 #include<algorithm>#include<vector> #include<string.h>using namespace std;const int MAX=1e3+5;vector<int>g[MAX],node[MAX];int n,s,k,pa[MAX],t;bool vis[MAX];void build(int u,int v,int d) //转化为以s为根的树 { ???pa[u]=v; ???int siz=g[u].size(); ???if(siz==1&&d>k) //度为1的为叶子结点 ????node[d].push_back(u); ?//按深度把u插入node中 ????for(int i=0;i<siz;i++) ???{ ???????int c=g[u][i]; ????????if(c!=v) build(c,u,d+1); ????}}void dfs(int u,int v,int d) //覆盖到服务器不超过k的节点 { ???vis[u]=1; ???int siz=g[u].size(); ???for(int i=0;i<siz;i++) ???{ ???????int c=g[u][i]; ???????if(c!=v&&d<k) ???????dfs(c,u,d+1); ???}}int solve(){ ???int ans=0; ???for(int d=n-1;d>k;d--) ???{ ???????for(int i=0;i<node[d].size();i++) //从叶子节点向上遍历 ????????{ ???????????int u=node[d][i]; ???????????if(vis[u]) continue; ???????????int v=u; ???????????for(int j=0;j<k;j++) ?//找到u的k级祖先 ????????????????u=pa[u]; ??????????????dfs(u,-1,0); //在u处放服务器，并覆盖u k级以内的子女 ???????????????ans++; ???????} ???} ???return ans; }int main(){ ???ios::sync_with_stdio(false); ???cin>>t; ???while(t--) ???{ ???????cin>>n>>s>>k; ???????memset(vis,0,sizeof(vis)); ???????for(int i=0;i<=n;i++) ???????{ ???????????g[i].clear(); ???????????node[i].clear(); ???????} ???????for(int i=0;i<n-1;i++) ???????{ ????????int a,b; ????????cin>>a>>b; ????????g[a].push_back(b); ?//vector实现邻接表 ?????????g[b].push_back(a); ???????} ????????build(s,-1,0); ???cout<<solve()<<endl; ???} ???return 0;}UVA 1267 Network
原文地址：http://www.cnblogs.com/Egoist-/p/7615753.html