28
hdu 4607 Park Visit dfs
這題題意很好理解，就是要找到個最大長度，比賽的時候就在糾結怎麼找，一開始想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));
}
}
}
最後更新：2017-04-03 16:48:42