UVA 11695 Flight Planning 修改一條邊使得樹的直徑最短

UVA 11695 Flight Planning 修改一條邊使得樹的直徑最短

題目鏈接：點擊打開鏈接

題意：

給定n(n<=2500) 節點的一棵樹

刪除一條邊再加入一條邊使得樹的直徑最短。

思路：首先枚舉刪除的那條邊，

然後計算出刪除後的2棵子樹各自的重心

則新建的邊一定是重心的連線。

而新的直徑要麼是在某個子樹中，要麼是兩個子樹間。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#include 
#include 
#include 
#include 
using namespace std;
#define pb push_back
const double inf = 1e9;
const int N = 2505;
struct Ans{
	int ans, oldx, oldy, nowx, nowy;
};
vectoredge[N];
void add(int u, int v){
	edge[u].push_back(v);
}
int n;
void init(){ for (int i = 0; i <= n; i++)edge[i].clear(); }
Ans a;
int dis[N], pre[N], far, badu, badv;
vectorG;
void bfs(int x){
	for (int i = 1; i <= n; i++)dis[i] = -1;
	pre[x] = -1;
	dis[x] = 0;
	queueq;
	q.push(x);
	far = x;
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int i = 0; i < edge[u].size(); i++){
			int v = edge[u][i];
			if (dis[v] != -1 || (min(u, v) == min(badu, badv) && max(u, v) == max(badu, badv)))continue;
			dis[v] = dis[u] + 1;
			pre[v] = u;
			q.push(v); 
			if (dis[far] < dis[v])far = v;
		}
	}
	G.clear();
	int tmp = far;
	while (tmp != -1){
		G.pb(tmp); tmp = pre[tmp];
	}
}

void work(){
	Ans d = {0, badu, badv, 0, 0 };
	int link = 1;
	bfs(badu);	bfs(far);
	link += (dis[far] + 1) / 2;
	d.nowx = G[G.size() / 2];
	d.ans = dis[far];

	bfs(badv);	bfs(far);
	d.nowy = G[G.size() / 2];
	link += (dis[far] + 1) / 2;
	d.ans = max(d.ans, dis[far]);
	d.ans = max(d.ans, link);
	if (d.ans < a.ans)a = d;
}
int l[N], r[N];
void input(){
	scanf("%d", &n);
	init();
	for (int i = 1, u, v; i < n; i++){
		scanf("%d %d", &u, &v);
		add(u, v); add(v, u);
		l[i] = u; r[i] = v;
	}
	a.ans = inf;
}
int main(){
	int T; scanf("%d", &T);
	while (T--){
		input();
		for (int i = 1; i < n; i++){
			badu = l[i]; badv = r[i];
			work();
		}
		printf("%d\n%d %d\n%d %d\n", a.ans, a.oldx, a.oldy, a.nowx, a.nowy);
	}
	return 0;
}
/*
2
4
1 2
2 3
3 4

14
1 2
1 8
2 3
2 4
8 9
8 10
8 11
4 5
4 6
4 7
10 12
10 13
13 14

*/