HDU 4607.Park Visit-树的直径(BFS版)+结论公式(乱推公式)-备忘(加油！)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Park Visit

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4814 Accepted Submission(s): 2100

Problem Description

Claire and her little friend, ykwd, are travelling in Shevchenko's Park! The park is beautiful - but large, indeed. N feature spots in the park are connected by exactly (N-1) undirected paths, and Claire is too tired to visit all of them. After consideration, she decides to visit only K spots among them. She takes out a map of the park, and luckily, finds that there're entrances at each feature spot! Claire wants to choose an entrance, and find a way of visit to minimize the distance she has to walk. For convenience, we can assume the length of all paths are 1.
Claire is too tired. Can you help her?

Input

An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with two integers N and M(1≤N,M≤10⁵), which respectively denotes the number of nodes and queries.
The following (N-1) lines, each with a pair of integers (u,v), describe the tree edges.
The following M lines, each with an integer K(1≤K≤N), describe the queries.
The nodes are labeled from 1 to N.

Output

For each query, output the minimum walking distance, one per line.

Sample Input

1
4 2
3 2
1 2
4 2
2
4

Sample Output

1
4

Source

2013 Multi-University Training Contest 1

题意就是给你一棵树，然后让你求k个点走一遍最短的路程，因为每个节点都有出口，所以不用再返回来。k个点是随意取的，只要求最短路径就可以。

思路就是先求一下树的直径，假设树的直径走过的节点为x个，如果k比x小，直接ans为k-1，如果大的话，就是树的直径+(k-直径节点数)*2就可以了。

公式我是随便测了几个数据然后猜出来的。。。

写的时候树的直径的板子错了，所以wa了几次。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m,cnt;//cnt为边数
int dist[maxn],head[maxn];//dist表示最长路，head为存图用的
bool vis[maxn]; struct node{//定义边的结构体
int from,to,val,next;
}edge[maxn<<];//注意是无向图，边数是二倍的 void init()//初始化，不可少
{
cnt=;
memset(head,-,sizeof(head));
} void addedge(int u,int v,int w)
{
edge[cnt].from=u;//起点
edge[cnt].to=v;//终点
edge[cnt].val=w;//权值
edge[cnt].next=head[u];//指向下一条边
head[u]=cnt++;
} int length;//最终的最长路径(树的直径)
int node;//记录端点值 void bfs(int s)
{
queue<int>q;//定义队列
memset(vis,false,sizeof(vis));//初始化，清零
memset(dist,,sizeof(dist));
q.push(s);//入列
vis[s]=true;//记录为遍历过的点
length=;
node=s;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-;i=edge[i].next){//遍历每一条边
int v=edge[i].to;
if(!vis[v]&&dist[v]<dist[u]+edge[i].val){
vis[v]=true;
dist[v]=dist[u]+edge[i].val;//到v的最长路径
if(length<dist[v]){
length=dist[v];//不断更新最长路径
node=v;//更新节点
}
q.push(v);//重新入列，寻找下一个点
}
}
}
} int main()
{
int t;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
int u,v,val;
scanf("%d%d",&u,&v);
val=;//路径权值
addedge(u,v,val);
addedge(v,u,val);
}
bfs();//第一遍找到距离最远的端点
bfs(node);//第二遍找最长距离
int x=length+;//x为树的直径的节点个数
while(m--){
int k;
scanf("%d",&k);
if(k<=x) printf("%d\n",k-);//如果比树的直径短
else{
int ans=length+(k-x)*;
printf("%d\n",ans);
}
}
}
return ;
} /*
1
19 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 12
12 13
9 14
14 15
15 16
5 10
5 11
10 17
17 18
17 19 7
6 10
9 11
11 12
13 15
19 */