首页 > 代码库 > hdu 4607 Park Visit 求树的直径
hdu 4607 Park Visit 求树的直径
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4607
题目大意:给你n个点,n-1条边,将图连成一棵生成树,问你从任意点为起点,走k(k<=n)个点,至少需要走多少距离(每条边的距离是1);
思路:树形dp求树的直径r;
a:若k<=r+1 ,ans = k-1;
b:若k>=r+1,ans = r+(k-(r+1))*2;
#include "stdio.h" #include "string.h" #define N 110000 struct node { int x,y; bool visit; int next; } edge[2*N]; int idx,head[N]; inline int MAX(int a,int b) { return a>b?a:b; } void Init() { idx=0; memset(head,-1,sizeof(head)); } void Add(int x,int y) { edge[idx].x=x; edge[idx].y=y; edge[idx].visit=false; edge[idx].next=head[x]; head[x]=idx++; } int n; int maxn[N],smaxn[N]; void DFS(int x) { int i,y; maxn[x] = smaxn[x] = 0; for(i=head[x]; i!=-1; i=edge[i].next) { y = edge[i].y; if(edge[i].visit) continue; edge[i].visit = edge[i^1].visit = true; DFS(y); if(maxn[y]+1>maxn[x]) { smaxn[x] = maxn[x]; maxn[x] = maxn[y]+1; } else if(maxn[y]+1>smaxn[x]) smaxn[x] = maxn[y]+1; } } int main() { int T,Q; int i,j; int x,y,k; scanf("%d",&T); while(T--) { Init(); scanf("%d%d",&n,&Q); for(i=1; i<n; ++i) { scanf("%d %d",&x,&y); Add(x,y); Add(y,x); } DFS(1); int D=0; //树的直径 for(i=1; i<=n; ++i) D = MAX(D,maxn[i]+smaxn[i]); D++; while(Q--) { scanf("%d",&k); if(k<=D) printf("%d\n",k-1); else printf("%d\n",D-1+(k-D)*2); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。