meeting（类似树的直径问题，两次bfs或树形dp）

68 阅读 0 评论 45 点赞

我是靠谱客的博主笑点低大侠，最近开发中收集的这篇文章主要介绍meeting（类似树的直径问题，两次bfs或树形dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/884/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

A new city has just been built. There're nnn interesting places numbered by positive numbers from 1to n.

In order to save resources, only exactly n−1 roads are built to connect these nnn interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered x1,x2…xk and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述:

First line two positive integers, n,k- the number of places and persons.

For each the following n−1 lines, there're two integers a,b that stand for a road connecting place aaa and bbb. It's guaranteed that these roads connected all nnn places.

On the following line there're kkk different positive integers x1,x2…xk separated by spaces. These are the numbers of places the persons are at.

输出描述:

A non-negative integer - the minimal time for persons to meet together.

示例1

输入

复制

输出

复制

说明

They can meet at place 1 or 3.

备注:

1≤n≤10^5

n个节点的树，树上有k个人，他们要到某个节点去吃饭，问最远的那个人要走的距离最短是多少

• 一句话题解：考虑距离最远的两个关键点，设它们的距离为d，d/2上取整即为答案。

• 必要性：这两个人要碰面，必然要走至少d/2步。

• 充分性：我们取两人路径中和一头距离为d/2上取整的一个点，让所有人在这相聚。如果有一个人在d/2时间内到不了，那么它和路径两头中与它远的那一头的距离大于d，与最远的假设矛盾。

• 找到这样最远的一对点类似找树的直径。可以直接dp，也可以采用两遍bfs：从任意一个关键点开始，找到离它最远的关键点x，再从x开始bfs，找到的新的最远点和x形成的就是直径。

• 当然对着题面直接dp也是可以做的，但是比较难写。

（大佬们好像都是写的树形dp,卑微）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+5;
bool vis[N];
bool book[N];
struct node{
int x,step;
node(){}
node(int _x,int _step){
x=_x;
step=_step;
}
};
vector<int> G[N];
int bfs1(int s){
int ans=0;
queue<node> q;
q.push(node(s,0));
while(!q.empty()){
node p=q.front();
q.pop();
int u=p.x;
vis[u]=true;
if(book[u]) ans=u;
for(int i=0;i<G[u].size();i++){
if(!vis[G[u][i]]){
q.push(node(G[u][i],p.step+1));
}
}
}
return ans;
}
int bfs2(int s){
memset(vis,0,sizeof(vis));
int ans=0;
queue<node> q;
q.push(node(s,0));
while(!q.empty()){
node p=q.front();
q.pop();
int u=p.x;
vis[u]=true;
if(book[u]) ans=p.step;
for(int i=0;i<G[u].size();i++){
if(!vis[G[u][i]]){
q.push(node(G[u][i],p.step+1));
}
}
}
return (ans+1)>>1;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int x;
for(int i=1;i<=m;i++){
scanf("%d",&x);
book[x]=true;
}
x=bfs1(x);
x=bfs2(x);
printf("%dn",x);
return 0;
}

树形dp过会补上

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int dp[N][3];
//dp[i][0]
v通过父亲获得的最长距离
//dp[i][1]
v在v的所有子树中获得的最长距离
//dp[i][2]
v的孩子的第二长距离
int id[N];
vector<int> G[N];
bool book[N];
void dfs1(int u,int fa){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue ;
dfs1(v,u);
if(book[v]){
if(dp[u][1]<dp[v][1]+1){
dp[u][1]=dp[v][1]+1;
id[u]=v;//记录点u的最大距离经过的第一个孩子节点
}
book[u]=true;
}
}
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
if(v==id[u]) continue;//找次大的
dp[u][2]=max(dp[u][2],dp[v][1]+1);
}
}
void dfs2(int u,int fa){
int ans;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
if(v==id[u]) dp[v][0]=max(dp[u][0],dp[u][2])+1;
else dp[v][0]=max(dp[u][0],dp[u][1])+1;
dfs2(v,u);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int x;
for(int i=1;i<=m;i++){
scanf("%d",&x);
book[x]=true;
}
dfs1(x,0);
dfs2(x,0);
int ans=INF;
for(int i=1;i<=n;i++){
ans=min(ans,max(dp[i][0],dp[i][1]));
}
printf("%dn",ans);
return 0;
}