jxy
2013-07-24
767浏览量
这题题意很好理解,就是要找到个最大长度,比赛的时候就在纠结怎么找,一开始想dfs怕超时,后来用并查集乱搞过了,看了标程果然是dfs,但只要2次就可以了,显然。
于是自己又敲了一遍
/* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #define INF 1E9 using namespace std; vector<int>node[100005]; int d[100005]; void dfs(int u,int f,int dp) { d[u]=dp; for(int i=0;i<node[u].size();i++) if(node[u][i]!=f)dfs(node[u][i],u,dp+1); } int main() { int T,n,m,k,K,i,v,u; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++)node[i].clear(); for(i=1;i<n;i++) { scanf("%d%d",&v,&u); node[u].push_back(v); node[v].push_back(u); } K=1; dfs(K,0,1); for(i=1;i<=n;i++) if(d[i]>d[K])K=i;//直径的一个端点 dfs(K,0,1); for(i=1;i<=n;i++) if(d[i]>d[K])K=i;//另一个端点 K=d[K]; while(m--) { scanf("%d",&k); if(k<=K)printf("%d\n",k-1); else printf("%d\n",K-1+2*(k-K)); } } }
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。