首页 > 代码库 > hdu4607 Park Visit(树的直径)
hdu4607 Park Visit(树的直径)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4607
题意:给定一棵树,从树中的任意选一个顶点出发,遍历K个点的最短距离是多少?(每条边的长度为1)
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=1e5+5; const int INF=0x3f3f3f3f; struct Edge { int v,l; int next; } edge[maxn<<2]; int vit[maxn],d[maxn]; int head[maxn],k; int node,ans; int n,m; void init() { k=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int l) { edge[k].v=v; edge[k].l=l; edge[k].next=head[u]; head[u]=k++; edge[k].v=u; edge[k].l=l; edge[k].next=head[v]; head[v]=k++; } void dfs(int u,int t) { for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(vit[v]==0) { vit[v]=1; d[v]=t+edge[i].l; if(d[v]>ans) { ans=d[v]; node=v; } dfs(v,d[v]); } } } int main() { int T; scanf("%d",&T); while(T--) { init(); scanf("%d%d",&n,&m); int l,r,len; for(int i=1; i<n; i++) { scanf("%d%d",&l,&r); addedge(l,r,1); } memset(vit,0,sizeof(vit)); vit[1]=1; ans=0; dfs(1,0); memset(vit,0,sizeof(vit)); vit[node]=1; ans=0; dfs(node,0); int k; for(int i=1; i<=m; i++) { scanf("%d",&k); if(k<=ans) printf("%d\n",k-1); else printf("%d\n",ans+(k-ans-1)*2); } } return 0; }
hdu4607 Park Visit(树的直径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。