poj 4607(ツリーの直径)
2135 ワード
テーマ:Park Visit
标题:一人で公園に行って、Kスポットを歩きたくて、最短距離を聞きます.
構想:木の直径(最長の鎖、最長の経路)を求める.任意の点Aから、Aから最も遠い点Bを見つける.Bから最も遠いCを見つけて、BCは最も長い経路です.Kコード:
标题:一人で公園に行って、Kスポットを歩きたくて、最短距離を聞きます.
構想:木の直径(最長の鎖、最長の経路)を求める.任意の点Aから、Aから最も遠い点Bを見つける.Bから最も遠いCを見つけて、BCは最も長い経路です.K
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
#define maxint 0x7fffffff
const int maxn = 100010;
int t, n, m, k;
int M, N, maxd;
int from, to;
vector <int> G[maxn];
bool vis[maxn];
inline void add_edge(int from, int to){
G[from].push_back(to);
G[to].push_back(from);
}
int dfs(int x, int d){
// cout << x << ' ' << d << endl;
int res = d;
vis[x] = 1;
if( maxd < d) {
N = x;
maxd = d;
}
for(int i = 0; i < G[x].size(); i ++){
if( vis[G[x][i]] ) continue;
res = max( res, dfs(G[x][i], d+1));
}
vis[x] = 0;
return res;
}
int solve(){
maxd = 0;
dfs(1, 0);
// cout << N << ' ' << maxd << endl;
return dfs(N, 0);
}
int main(){
// cin >> t;
scanf("%d",&t);
int from, to;
while(t --) {
memset(vis, 0, sizeof(vis));
for(int i = 0; i < maxn; i ++) G[i].clear();
// cin >> n >> m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n-1; i ++) {
// cin >> from >> to;
scanf("%d%d",&from, &to);
add_edge(from, to);
}
// system("pause");
solve();
maxd ++;
// cout << "maxlen " << maxlen << endl;
for(int i = 0; i < m; i ++) {
// cin >> k;
scanf("%d",&k);
if( k < maxd ) printf("%d
",k-1);
else printf("%d
",(k-maxd)*2+ maxd-1);
}
}
return 0;
}