首页 > 代码库 > Park Visit
Park Visit
hdu4607:http://acm.hdu.edu.cn/showproblem.php?pid=4607
题意:给你一棵树,树上每条边的权值是1,然后然你选择m个点,求遍历m个点的最小花费。
题解:这一题要用到树的性质。首先可以想到的是第一次肯定要选择一条最长的路径,也就是树的直径。至于其余的点怎么考虑呢?画个图可以知道,剩余的点的所产生的花费就是剩余点数的两倍,所以本题的关键就是求树的直径。求树的直径,是有方式的,就是两遍DFS,第一遍DFS找到一个当前点的最远的点,然后从这个最远的点开始,再进行一次DFS,得到的就是树的直径,这里距不证明了。可以用反正法。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 const int N=1e5+10; 8 vector<int>Q[N]; 9 int n,m,k,u,v;10 int maxn,start;11 void DFS(int u,int f,int len){12 if(len>maxn){13 maxn=len;14 start=u;15 }16 for(int i=0;i<Q[u].size();i++){17 if(f!=Q[u][i]){18 DFS(Q[u][i],u,len+1);19 }20 }21 }22 int main(){23 int cas;24 scanf("%d",&cas);25 while(cas--){26 scanf("%d%d",&n,&m);27 for(int i=1;i<=n;i++)28 Q[i].clear();29 for(int i=1;i<n;i++){30 scanf("%d %d",&u,&v);31 Q[u].push_back(v);32 Q[v].push_back(u);33 }34 start=0,maxn=0;35 DFS(1,0,0);36 maxn=0;37 DFS(start,0,0);38 for(int i=1;i<=m;i++){39 scanf("%d",&k);40 if(k<=maxn+1)41 printf("%d\n",k-1);42 else43 printf("%d\n",maxn+(k-1-maxn)*2);44 }45 }46 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。