3797714 2014 - 10 - 12 21:58 : 19
Accepted 3820 C++
1350 70240
zz_1215

比較麻烦的一道题吧，開始的时候不停的段异常，后面知道是爆栈了，然后用数组模拟递归，才ac了

思路挺简单的，先找到这个树的直径，单独拿出来，能够证明最后选的两个点一定是在直径上的。我就不证了

然后求出这条直径上的每一个点向外延伸的最远距离

对这个距离做两次RMQ，第一次是对于往左边计算最大距离，所以要这个距离的序列要依次+1，+2，+3.......+n-1，+n

第二次是对于往右边计算最大距离。所以序列要+n，+n-1........+3，+2，+1

然后确定一个左起点。二分右起点

最后的复杂度是O（n*log（n））

实现起来还是挺复杂的，吐槽下这样的考代码能力的题

最后有一点提醒下，向外延伸的时候不要忘了向父节点的方向延伸。由于这个我又wa了一次

#pragma comment(linker, "/STACK:102400000,102400000")

#include<iostream>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#include<cmath>

#include<cassert>

#include<cstring>

#include<iomanip>

using namespace std;

#ifdef _WIN32

#define i64 __int64

#define out64 "%I64d\n"

#define in64 "%I64d"

#else

#define i64 long long

#define out64 "%lld\n"

#define in64 "%lld"

#endif

/************ for topcoder by zz1215 *******************/

#define foreach(c,itr)  for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)

#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)

#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)

#define S64(a)          scanf(in64,&a)

#define SS(a)           scanf("%d",&a)

#define LL(a)           ((a)<<1)

#define RR(a)           (((a)<<1)+1)

#define pb              push_back

#define pf              push_front

#define X               first

#define Y               second

#define CL(Q)           while(!Q.empty())Q.pop()

#define MM(name,what)   memset(name,what,sizeof(name))

#define MC(a,b)		memcpy(a,b,sizeof(b))

#define MAX(a,b)        ((a)>(b)?

(a):(b))

#define MIN(a,b)        ((a)<(b)?(a):(b))

#define read            freopen("out.txt","r",stdin)

#define write           freopen("out2.txt","w",stdout)

const int inf = 0x3f3f3f3f;

const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;

const double oo = 10e9;

const double eps = 10e-9;

const double pi = acos(-1.0);

const int maxn = 211111;

struct Node{

	int now;

	int to;

	int h;

	bool operator < (const Node & cmp) const{

		return h>cmp.h;

	}

}node;

int n;

vector<Node>g[maxn];

int dfv[maxn];

int dfn[maxn];

int t[maxn];

int h[maxn];

int df;

vector<int>s;

vector<int>si;

bool vis[maxn];

vector<int>line;

int a[maxn];

int ax[maxn][20];

int dx[maxn][20];

int lg2[maxn];

bool isline[maxn];

void dfs(){

	for (int i = 1; i <= n; i++){

		vis[i] = false;

	}

	df = 1;

	s.clear();

	si.clear();

	s.push_back(1);

	si.push_back(0);

	vis[1] = true;

	int now, to, id;

	while (!s.empty()){

		now = s.back();

		id = si.back();

		if (id < g[now].size()){

			to = g[now][id].to;

			si.back()++;

			if (!vis[to]){

				vis[to] = true;

				t[to] = now;

				s.push_back(to);

				si.push_back(0);

			}

		}

		else{

			dfv[df] = s.back();

			dfn[s.back()] = df++;

			s.pop_back();

			si.pop_back();

		}

	}

}

int find_len(int now){

	if (g[now].size() >= 2){

		return g[now][0].h + g[now][1].h;

	}

	else if (g[now].size() == 1){

		return g[now][0].h;

	}

	else{

		return 0;

	}

}

void get_line(int now){

	if (g[now].size() >= 2){

		int t1 = g[now][0].to;

		int t2 = g[now][1].to;

		isline[now] = true;

		while (true){

			isline[t1] = true;

			line.push_back(t1);

			if (g[t1].size() > 0){

				t1 = g[t1][0].to;

			}

			else{

				break;

			}

		}

		reverse(line.begin(), line.end());

		line.push_back(now);

		while (true){

			isline[t2] = true;

			line.push_back(t2);

			if (g[t2].size() > 0){

				t2 = g[t2][0].to;

			}

			else{

				break;

			}

		}

	}

	else if(g[now].size() ==1){

		while (true){

			isline[now] = true;

			line.push_back(now);

			if (g[now].size() > 0){

				now = g[now][0].to;

			}

			else{

				break;

			}

		}

	}

}

int max_way(int now){

	int to;

	int re = 0;

	for (int i = 0; i < g[now].size(); i++){

		to = g[now][i].to;

		if (!isline[to]){

			re = max(re, g[now][i].h);

		}

	}

	return re;

}

void sparse_table(){

	for (int i = 0; i < line.size(); i++){

		ax[i][0] = a[i]+i;

		dx[i][0] = a[i]+(int)line.size()-1-i;

	}

	for (int step = 1; (1 << step) < line.size(); step++){

		for (int i = 0; i < line.size(); i++){

			ax[i][step] = ax[i][step - 1];

			dx[i][step] = dx[i][step - 1];

			if (i + (1 << (step - 1)) < line.size()){

				ax[i][step] = max(ax[i][step], ax[i + (1 << (step - 1))][step - 1]);

				dx[i][step] = max(dx[i][step], dx[i + (1 << (step - 1))][step - 1]);

			}

		}

	}

}

int max_a(int l, int r){

	return max(ax[l][lg2[r - l + 1]], ax[r - (1 << lg2[r - l + 1]) + 1][lg2[r - l + 1]]);

}

int max_d(int l, int r){

	return max(dx[l][lg2[r - l + 1]], dx[r - (1 << lg2[r - l + 1]) + 1][lg2[r - l + 1]]);

}

int find(int l, int r){

	int mid = (r + l) / 2;

	return max(max_a(l, mid) - l, max_d(mid+1,r)-( (int)line.size()-1-r ) );

}

int back[maxn];

void find_back(){

	for (int i = 1; i <= n; i++){

		back[i] = 0;

	}

	queue<int>q;

	q.push(1);

	int now, to,fa,temp;

	while (!q.empty()){

		now = q.front();

		q.pop();

		if (t[now]){

			fa = t[now];

			back[now] = 1 + back[fa];

			temp = 0;

			if (g[fa][0].to == now){

				if (g[fa].size() >= 2){

					temp = g[fa][1].h+1;

				}

			}

			else{

				temp = g[fa][0].h;

			}

			back[now] = max(back[now], temp);

		}

		for (int i = 0; i < g[now].size(); i++){

			q.push(g[now][i].to);

		}

	}

}

void start(){

	dfs();

	for (int i = 1; i <= n; i++){

		h[i] = 0;

	}

	vector<Node>gg;

	int now, to;

	for (now = 1; now <= n; now++){

		gg.clear();

		for (int i = 0; i < g[now].size(); i++){

			to = g[now][i].to;

			if (to != t[now]){

				gg.push_back(g[now][i]);

			}

		}

		g[now] = gg;

	}

	for (int x = 1; x < df; x++){

		now = dfv[x];

		for (int i = 0; i < g[now].size(); i++){

			to = g[now][i].to;

			h[now] = max(h[now], h[to] + 1);

		}

	}

	for (now = 1; now <= n; now++){

		for (int i = 0; i < g[now].size(); i++){

			to = g[now][i].to;

			g[now][i].h = h[to] + 1;

		}

	}

	for (now = 1; now <= n; now++){

		sort(g[now].begin(), g[now].end());

	}

	int id;

	int len = -1;

	int temp;

	for (now = 1; now <= n; now++){

		temp = find_len(now);

		if (temp > len){

			len = temp;

			id = now;

		}

	}

	for (int i = 1; i <= n; i++){

		isline[i] = false;

	}

	line.clear();

	get_line(id);

	find_back();

	for (int i = 0; i < line.size(); i++){

		a[i] = max_way(line[i]);

		if (line[i] == id){

			a[i] = max(a[i], back[id]);

		}

	}

	sparse_table();

	int ans=inf;

	int left;

	int right;

	int l, r;

	for (int lend = 0; lend < line.size(); lend++){

		l = lend;

		r = line.size() - 1;

		while (l + 2 < r){

			int mid = (l + r) / 2;

			if (find(lend, mid) > (int)line.size() - 1 - mid){

				r = mid;

			}

			else{

				l = mid;

			}

		}

		for (int x = l; x <= r; x++){

			temp = max(find(lend, x), (int)line.size() - 1 - x);

			temp = max(temp, lend);

			if (temp < ans){

				ans = temp;

				left = lend;

				right = x;

			}

		}

	}

	cout << ans << " " << line[left] << " " << line[right] << endl;

}

int main(){

	for (int i = 0; i < 20; i++){

		if ((1 << i) < maxn){

			lg2[1 << i] = i;

		}

	}

	for (int i = 3; i < maxn; i++){

		if (!lg2[i]){

			lg2[i] = lg2[i - 1];

		}

	}

	int T;

	cin >> T;

	while (T--){

		cin >> n;

		for (int i = 1; i <= n; i++){

			g[i].clear();

		}

		node.h = 0;

		for (int i = 1; i <= n - 1; i++){

		//	cin >> node.now >> node.to;

			SS(node.now); SS(node.to);

			g[node.now].push_back(node);

			swap(node.now, node.to);

			g[node.now].push_back(node);

		}

		start();

	}

	return 0;

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。

最新文章

  1. ios .a和.framework
  2. 【JVM】JVM系列之内存模型（六）
  3. Oracle行内链接不会引起USER_TABLES中CHAIN_CNT值变化
  4. Selenium_用selenium webdriver实现selenium RC中的类似的方法
  5. Java随学随记
  6. 使用openssl库实现RSA、AES数据加密
  7. 个推推送Android问题检测
  8. List&lt;T&gt;.Sort() 排序的用法
  9. JDBC链接
  10. webpack入门学习
  11. 我的小前端 （2）—— JQ和zepto
  12. ubuntu 安装Opencv2.4.7
  13. Get started - UIkit documentation
  14. js控制键盘按键(回车、空格)
  15. Java自定义注解及使用
  16. 201521123116 《java程序设计》第十三周学习总结
  17. Python学习之再议row_input
  18. Python调用subprocess.Popen卡死的解决方案
  19. Java 深拷贝，浅拷贝
  20. 如何实现.net程序的进程注入

热门文章

  1. Android -&amp;gt; 怎样避免Handler引起内存泄露
  2. 约瑟夫问题--list模拟循环链表
  3. zoj3201（树形dp）
  4. 用XAML做网页！！—开篇
  5. SWT的TableVierer的使用三(数据筛选和着色)
  6. linux进程解析--进程的退出及销毁
  7. 浅析JAVA设计模式之工厂模式(一)
  8. android--自己定义ProgressDialog显示位置(其他Dialog子类都能够设置)
  9. 每日回顾Shell —cat,tail,head
  10. Why 使用TLS记录封装IP层VPN IS A Bad Idea