原题
题意：
一个多边形，三角剖分，求一条对角线最多能经过多少三角形
题解：
因为不涉及坐标之类的，所以根几何肯定一点关系都没有。
我们会发现，对于有共边的两个三角形，可以被同一条线穿过，而这就相当于这两个三角形之间有边。然后因为是多边形的三角剖分，所以最后只会有n-1条边。这样我们得到的就是一棵树了！
然后呢，因为我们要求的是任意一条对角线经过最多的城市个数，显然，这就是要求树上最长的一条路径，也就是树的直径了！
至于O(log)连边 ，考虑用pair将边和所属编号记录在map里，查询时连边即可（因为一条边最多被覆盖两次，所以想变快可以在该边被覆盖后将map中erase）
洛谷不开O2很慢……开O2很快……
#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#define N 200010
#define MP(x,y) make_pair(x,y)
using namespace std;
int n,dep[N],t,cnt=1,head[N];
queue <int> q;
bool vis[N];
map < pair<int,int> , int > mp;
struct hhh
{
int to,next;
}edge[2*N];
int read()
{
int ans=0,fu=1;
char j=getchar();
for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;
for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
return ans*fu;
}
void add(int u,int v)
{
edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
edge[cnt].to=u;edge[cnt].next=head[v];head[v]=cnt++;
}
int bfs(int s)
{
dep[s]=1;
memset(vis,0,sizeof(vis));
vis[s]=1;
int mx=0;
q.push(s);
while (!q.empty())
{
int r=q.front();
q.pop();
if (dep[r]>mx) t=r,mx=dep[r];
for (int i=head[r];i;i=edge[i].next)
{
if (vis[edge[i].to]) continue;
q.push(edge[i].to);
vis[edge[i].to]=1;
dep[edge[i].to]=dep[r]+1;
}
}
return mx;
}
int main()
{
n=read();
for (int i=1,a,b,c;i<n-1;i++)
{
a=read(),b=read(),c=read();
if (mp[MP(min(a,b),max(a,b))]) add(mp[MP(min(a,b),max(a,b))],i);
else mp[MP(min(a,b),max(a,b))]=i;
if (mp[MP(min(a,c),max(a,c))]) add(mp[MP(min(a,c),max(a,c))],i);
else mp[MP(min(a,c),max(a,c))]=i;
if (mp[MP(min(c,b),max(b,c))]) add(mp[MP(min(c,b),max(b,c))],i);
else mp[MP(min(c,b),max(b,c))]=i;
}
bfs(1);
printf("%d\n",bfs(t));
return 0;
}