记录编号	139949	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 旅游	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.850 s
提交时间	2014-11-17 20:21:15	内存使用	3.37 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=200010;
int N;
class DIAG{
public:
	int a,b;
	int id;
};
bool operator < (DIAG x,DIAG y){
	if(x.a==y.a) return x.b<y.b;
	return x.a<y.a;
}
DIAG assign_diag(int a,int b,int id){
	DIAG e;
	e.a=a,e.b=b,e.id=id;
	return e;
}
vector<DIAG> diags;
void add_diag(int a,int b,int id){
	if(a>b) swap(a,b);
	if(a==1&&b==N) return;
	if(b-a==1) return;
	diags.push_back(assign_diag(a,b,id));
}
vector<int> c[SIZEN];
void addedge(int a,int b){
	c[a].push_back(b);
	c[b].push_back(a);
}
int f[SIZEN];
queue<int> Q;
pair<int,int> BFS(int s){//最长路到哪,最长路含节点数
	memset(f,-1,sizeof(f));
	while(!Q.empty()) Q.pop();
	f[s]=0;Q.push(s);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(f[u]==-1){
				f[u]=f[x]+1;
				Q.push(u);
			}
		}
	}
	int ans=0,ansid=0;
	for(int i=1;i<=N-2;i++){
		if(f[i]>ans){
			ans=f[i];
			ansid=i;
		}
	}
	return make_pair(ansid,ans+1);
}
void work(void){
	sort(diags.begin(),diags.end());
	for(int i=0;i<diags.size();i+=2) addedge(diags[i].id,diags[i+1].id);
	int s=BFS(1).first;
	printf("%d\n",BFS(s).second);
}
void read(void){
	scanf("%d",&N);
	int a,b,c;
	for(int i=1;i<=N-2;i++){
		scanf("%d%d%d",&a,&b,&c);
		add_diag(a,b,i);
		add_diag(b,c,i);
		add_diag(a,c,i);
	}
}
int main(){
	freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
	read();
	work();
	return 0;
}