题目
到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~
经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。
为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？
输入格式
每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数N，N的含义如题目所述。
接下来有N-2行，每行包含三个整数 p,q,r，表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。
输出格式
输出文件共包含1行，表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)
输入样例
6
1 2 4
2 3 4
1 4 5
1 5 6
输出样例
4
提示
4<=N<=200000
题解
题意：找一条对角线使经过尽量多的三角形
平面图联想到对偶图，发现对偶图是棵树，答案就是树的直径
建图时，将每个三角行的三条边放在一起排序，相同的边最多有两个，且这两个就是相邻的三角形
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 200005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int h[maxn],ne = 2;
struct EDGE{int to,nxt;}ed[maxn << 1];
inline void build(int u,int v){
ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;
}
struct line{
int a,b,id;
}e[maxn * 3];
inline bool operator < (const line& a,const line& b){
return a.a == b.a ? a.b < b.b : a.a < b.a;
}
int n,m,vis[maxn],d[maxn],q[maxn];
void order(int& a,int& b,int& c){
if (a > b) swap(a,b);
if (a > c) swap(a,c);
if (b > c) swap(b,c);
}
int head,tail;
void solve(){
q[head = tail = 1] = 1;
int u,rt = 1; vis[1] = true;
while (head <= tail){
u = q[head++];
if (d[u] > d[rt]) rt = u;
Redge(u) if (!vis[to = ed[k].to]){
d[to] = d[u] + 1; vis[to] = true;
q[++tail] = to;
}
}
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
q[head = tail = 1] = rt; d[rt] = 1; vis[rt] = true;
while (head <= tail){
u = q[head++];
if (d[u] > d[rt]) rt = u;
Redge(u) if (!vis[to = ed[k].to]){
d[to] = d[u] + 1; vis[to] = true;
q[++tail] = to;
}
}
printf("%d\n",d[rt]);
}
int main(){
n = read();
int a,b,c;
REP(i,n - 2){
a = read(); b = read(); c = read();
order(a,b,c);
e[++m] = (line){a,b,i};
e[++m] = (line){b,c,i};
e[++m] = (line){a,c,i};
}
sort(e + 1,e + 1 + m);
for (int i = 1; i <= m; i++){
if (e[i].a == e[i - 1].a && e[i].b == e[i - 1].b)
build(e[i].id,e[i - 1].id);
}
solve();
return 0;
}