题解 P2610 【[ZJOI2012]旅游】
先上结论
这道题仔细想想会发现，如果把每个三角形看作一个节点，领边看作一条边，那么最后生成的图一定是一个二叉树。 当然，其实二不二叉都不影响。 关键是如何证明这个结论。
然后上证明
嗯哼，这个道理其实很简单，但是我还是说一下。 首先，整个图是肯定联通的，毕竟本来就是一个多边形，它转换成图后肯定不存在独立的部分。 而且注意到一个特点，一个n边形能且只能分成n-2个三角形，且无论怎么分都只用连接n-3条对角线。 而在这道题中，每一条被连接起来的对角线，都等于生成图中的一条连边。 所以一共n-2个点，n-3条边。 再加上树上是不可能出现环的，而这道题中，如果形成了环，那肯定是一圈的三角形把一个点围了起来，然而节点都必须在边上，所以不可能形成环。 呐呐，由上可知证毕。 之后，我们知道了这是一个什么图，该思考怎样去算出答案。
注意到
我们的路线必须与一个城市至少有两个交点，才算是经过了这个城市，因此只经过一个顶点是没用的。 而且，我们的路线是一条线段，也就是说无法折返。由于这是一个凸多边形，至少不用担心走不过去的问题，那么问题就在于什么样的路线才是最优的。
又上结论
如果我们走生成图上的树的直径，那么一定是最优的。（你肯定知道树的直径是啥吧） 为什么？ 因为我们无法折返，就相当于在树上走一条简单路径，因此最长的路肯定就是直径辣。
如何实现
我们注意到n的范围是20万，有点大，显然用数组记录三角形的邻边是肯定会炸的。但是我们有STL啊！ 于是乎，pair套map映射就呼之欲出了。 至于如何找树的直径，那啥，直接O(n)dfs两遍就完事儿辣。如果不明白为什么。。。请百度（or谷歌）！。
最后上代码
#include<bits/stdc++.h>
#define fr(i,a,b) for(int i=a;i<=b;++i)
#define pr(i,a,b) for(int i=a;i>=b;--i)
#define fh(i,a,b) for(int i=head[a],b=e[i].to;i;i=e[i].last,b=e[i].to)
#define pp puts("")
#define xiu return
using namespace std;
typedef double lf;
typedef long long ll;
const int N = 2e5+10,M = 110,inf = 1e9+7;
const lf eps = 1e-5;
template <class T> void read(T &w){
w=0;int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){(w*=10)+=ch-'0';ch=getchar();}
w*=f;
}
template <class T> void write(T w){
if(w<0){putchar('-');w*=-1;}
if(w/10) write(w/10);
putchar(w%10+'0');
}
map <pair<int,int>,int> ys;
struct edg{int last,to;}e[N<<1];
int n,m,cur=1,head[N],deep[N],root,ans;
void add(int x,int y){
e[++cur]=(edg){head[x],y};head[x]=cur;
e[++cur]=(edg){head[y],x};head[y]=cur;
}
void dfs(int x,int y){
deep[x]=deep[y]+1;
fh(i,x,u){
if(u==y) continue;
dfs(u,x);
}
}
int main(){
read(n);
fr(i,1,n-2){
int p,q,r;
read(p);read(q);read(r);
if(q>p) swap(p,q);
if(r>p) swap(p,r);
if(r>q) swap(q,r);//那啥，排个序去重....少写了3个if+else，而且还省时间空间....
if(!ys[pair<int,int>(p,q)]){
ys[pair<int,int>(p,q)]=i;
}
else
add(i,ys[pair<int,int>(p,q)]);
if(!ys[pair<int,int>(p,r)]){
ys[pair<int,int>(p,r)]=i;
}
else
add(i,ys[pair<int,int>(p,r)]);
if(!ys[pair<int,int>(q,r)]){
ys[pair<int,int>(q,r)]=i;
}
else
add(i,ys[pair<int,int>(q,r)]);
}
root=1;
dfs(1,0);
fr(i,2,n-2)
if(deep[i]>deep[root])
root=i;
dfs(root,0);
fr(i,1,n-2)
if(deep[i]>ans)
ans=deep[i];
write(ans);pp;
xiu 0;
}哈哈一遍A无调试~