poj 4607(ツリーの直径)

2135 ワード

テーマ:Park Visit
标题:一人で公園に行って、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; }