到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~
经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。
为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？
到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~
经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。
4<=N<=200000
巧妙的建图+树的直径~
有n-2个三角形，他们中间用n-3条边隔开，我们把三角形看作点，有公共边的三角形连边，就构成一棵树了！
因为树上两个点之间的边与图中两个三角形的公共边一一对应，因此在树上走一条边相当于在图中走一条公共边，；
而走一条公共边两个三角形都经过两次了，表示到达了两个城市。
所以问题就变成了求树的最长链即树的直径。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map<pair<int,int>,int> mp;
int n,dp[200005],siz[200005];
vector<int> e[200005];
int a[4],ans;
void build(int pos,int x,int y)
{
int st;
st=mp[make_pair(x,y)];
if(st)
{
e[st].push_back(pos);
e[pos].push_back(st);
}
else
mp[make_pair(x,y)]=pos;
}
void dfs(int u,int father)
{
siz[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==father)
continue;
dfs(v,u);
ans=max(ans,siz[u]+siz[v]);
siz[u]=max(siz[u],siz[v]+1);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-2;i++)
{
scanf("%d%d%d",&a[1],&a[2],&a[3]);
sort(a+1,a+1+3);
build(i,a[1],a[2]);
build(i,a[2],a[3]);
build(i,a[1],a[3]);
}
dfs(1,-1);
printf("%d\n",ans);
return 0;
}
原文：http://www.cnblogs.com/water-full/p/4515961.html