10W个点的一棵树,边权为1
求访问K个点要走过的最小路程
BFS求出一条最长路以后,我们可以YY出其他的边都要重复走两次
树上的最长路可以从任意一点开始BFS求出这点的最大距离,再把终点设置为起点再做一次BFS
所以就判断K和最长路间的距离就行了 O(n) 算法
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
//typedef long long LL;
//typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
#define EPS 1e-8
#define MAXN 100005
#define MAXE 200005
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define MOD 1000000007
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define mabs(a) (((a) < 0) ? (-a) : (a))
#define YES cout<<"YES"<<endl;
#define L(t) (t << 1)
#define R(t) (t << 1 | 1)
#define Mid(a,b) ((a+b)>>1)
#define lowbit(a) (a&-a)
#define FOR(a,b,c) for(int a = b; a < c; a++)
#define FOR2(a,b,c) for(int a = b; a <= c; a++)
#define LOOP(a,b) for(int lop = a; lop < b; lop++)
#define LOOP2(a,b) for(int lop = a; lop <= b; lop++)
//int gcd(int a,int b){ return b?gcd(b,a%b):a; }
//int lcm(int a,int b){ return a*b/gcd(a,b); }
struct Edge
{
int u,v,w; // st,ed,value
int next;
}edge[MAXE];
struct Point
{
int p;
int dis;
Point(int a,int b)
{
p = a;
dis = b;
}
};
int head[MAXN];
bool vis[MAXN];
int cnt ; // num of edge
int n ; // num of point
int m ;
void add(Edge x)
{
edge[cnt].u = x.u;
edge[cnt].v = x.v;
edge[cnt].w = x.w;
edge[cnt].next = head[x.u];
head[x.u] = cnt++;
edge[cnt].v = x.u;
edge[cnt].u = x.v;
edge[cnt].w = x.w;
edge[cnt].next = head[x.v];
head[x.v] = cnt++;
}
int endp;
int bfs(int s)
{
int dis = -INF;
queue<Point> q;
Point p(s,);
q.push(p);
vis[s] = true;
while(!q.empty())
{
int u = q.front().p;
int d = q.front().dis;
if(d > dis)
{
dis = max(dis,d);
endp = u;
}
for(int i = head[u]; i != -; i = edge[i].next)
{
if(!vis[edge[i].v])
{
q.push(Point(edge[i].v,d+));
vis[edge[i].v] = true;
}
}
q.pop();
}
return dis;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// std::ios::sync_with_stdio(false);
int t;
scanf("%d",&t);
while(t--)
{
cnt = ;
scanf("%d%d",&n,&m);
memset(vis,,sizeof(vis));
memset(edge,,sizeof(edge));
memset(head,-,sizeof(head));
for(int i = ; i < n- ; i++)
{
int a,b;
scanf("%d%d",&a,&b);
Edge E;
E.u = a;
E.v = b;
add(E);
}
int dis1 = bfs();
memset(vis,,sizeof(vis));
int dis = bfs(endp);
for(int i = ; i < m ; i++)
{
int k;
scanf("%d",&k);
if(k- <= dis) printf("%d\n",k-);
else printf("%d\n",dis+*(k-dis-));
}
}
return ;
}