网络（Network,Seoul 2007,LA 3902）

本文主要是介绍网络（Network,Seoul 2007,LA 3902），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：https://icpcarchive.ecs.baylor.edu/external/39/3902.html

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;const int maxn=1000+10;
vector<int> gr[maxn],nodes[maxn];
int n,s,k,fa[maxn];
bool covered[maxn];//无根树转有根树，计算fa数组，根据深度把叶子结点出入nodes表中
void dfs(int u,int f,int d){fa[u]=f;int nc=gr[u].size();if(nc==1&&d>k) nodes[d].push_back(u);for(int i=0;i<nc;i++){int v=gr[u][i];if(v!=f) dfs(v,u,d+1);}
}void dfs2(int u,int f,int d){covered[u]=true;int nc=gr[u].size();for(int i=0;i<nc;i++){int v=gr[u][i];if(v!=f&&d<k) dfs2(v,u,d+1);//只覆盖到新服务器距离不超过k的结点}
}int solve(){int ans=0;memset(covered,0,sizeof(covered));for(int d=n-1;d>k;d--)for(int i=0;i<nodes[d].size();i++){int u=nodes[d][i];if(covered[u]) continue;   //只覆盖到新服务器距离不超过k的结点int v=u;for(int j=0;j<k;j++) v=fa[v];//v是u的k级祖先dfs2(v,-1,0);//在结点v放服务器ans++;}return ans;
}int main(){int T;cin>>T;while(T--){cin>>n>>s>>k;for(int i=1;i<=n;i++) {gr[i].clear();nodes[i].clear();}for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;gr[a].push_back(b);gr[b].push_back(a);}dfs(s,-1,0);cout<<solve()<<endl;}return 0;
}

这篇关于网络（Network,Seoul 2007,LA 3902）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---