NC14303. X-Men
描述
输入描述
The first line is the number of test cases.
For each test case, the first line contains two positive numbers N(1 ≤ N ≤ 103), M(1 ≤ M ≤ 103). The second line contains M numbers ai (1 ≤ ai ≤ N).
The following N - 1 lines describe the roads. Each line contains two integers u, v (1 ≤ u,v ≤ N), denoting there is a road between city u and city v.
输出描述
For each test case, output one number in one single line representing the answer. You should output your answer rounded to two decimal places.
示例1
输入:
2 7 3 5 6 7 1 2 1 3 1 4 5 2 6 3 4 7 3 3 1 1 2 1 2 2 3
输出:
2.00 0.00
说明:
In the first example, each X-man only have one adjacent city can be chosen to move in the first hour. They will move from city {5, 6, 7} to city {2, 3, 4} respectively. Each X-man only have one adjacent city can be chosen to move in the second hour, too. They will all move to city {1}. And then all of them can't feel any X-man such that distance between two X-men is more than one unit length. So they will be arrested immediately after two hours from the beginning to now. This is the only situation. So the answer is {2/1 = 2.00}.C 解法, 执行用时: 54ms, 内存消耗: 4264K, 提交时间: 2022-05-01 16:23:14
#include <stdio.h>
#include <string.h>
_Bool M[1005]={0};
int N[1005][1005]={0};
int n,m,a,t_=0;
void dfs(int u,int v,int len)
{
if(M[u]&&t_<len)
t_=len;
for(int i=1;i<=N[u][0];i++)
{
if(N[u][i]&&N[u][i]!=v)
dfs(N[u][i],u,len+1);
}
}
int main()
{
scanf("%d",&a);
while(a--)
{
memset(M,0,sizeof(M));
memset(N,0,sizeof(N));
scanf("%d%d",&n,&m);
for(int i=1,temp=0;i<=m;i++)
{
scanf("%d",&temp);
M[temp]=1;
}
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
N[u][0]++;
N[v][0]++;
N[u][N[u][0]]=v;
N[v][N[v][0]]=u;
}
t_=0;
for(int i=1;i<=n;i++)
if(M[i])
dfs(i,0,0);
printf("%d.00\n",t_/2);
}
return 0;
}
C++(clang++11) 解法, 执行用时: 37ms, 内存消耗: 588K, 提交时间: 2020-12-24 20:06:53
#include<bits/stdc++.h>
using namespace std;
vector<int> G[1005];
int x,y,ans,vis[1005],m,n,t,v;
void dfs(int x,int y,int len)
{
if (vis[x]) ans=max(ans,len);
for (int i=0;i<G[x].size();i++)
{
v=G[x][i];
if (v==y) continue;
dfs(v,x,len+1);
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
G[i].clear();
}
memset(vis,0,sizeof(vis));
for (int i=1;i<=m;i++)
{
cin>>x;
vis[x]=1;
}
for (int i=1;i<n;i++)
{
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
ans=0;
for (int i=1;i<=n;i++)
if (vis[i]) dfs(i,0,0);
printf("%d.00\n",ans/2);
}
}