题目大意
给出一个凸$n$边形,按顺时针给予顶点编号为$[1,n]$
如今把这个凸$n$边形划分成$n-2$个三角形,给出这些三角形的三个顶点编号
询问两个不相邻顶点间的路径最多可以经过多少个三角形(路径中包含一个三角形的一条边视作经过这个三角形)
数据范围
$4\leqslant n\leqslant 200000$
题解
跑暴力强行搜索肯定不能通过这道题的,因此我们要转换一下建图的方法
我们想到如果是一个凸$n$边形划分成的三角形,把它视作顶点,邻边视作连接两个相邻三角形的边,那么原图就肯定可以转化为一棵树
然后跑一遍树的直径即可
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,dia,et,top;
struct side{int mn,mx,id;}s[600500];
struct edge{int to,next;}e[400500];
int last[200500];
inline int cmp(side a,side b){return a.mn==b.mn?a.mx<b.mx:a.mn<b.mn;}
inline void insert(int a,int b,int id){s[++top]=(side){min(a,b),max(a,b),id};}
inline void addedge(int u,int v){
e[++et]=(edge){v,last[u]};last[u]=et;
e[++et]=(edge){u,last[v]};last[v]=et;
}
int dfs(int x,int fa){
int mx1=0,mx2=0;
goedge(i,x){
if (e[i].to==fa) continue;
int sum=dfs(e[i].to,x)+1;
if (sum>mx1) mx2=mx1,mx1=sum;
else if (sum>mx2) mx2=sum;
}
if (dia<mx1+mx2) dia=mx1+mx2;
return mx1;
}
int main(){
n=read();
For(i,1,n-2){
int p=read(),q=read(),r=read();
insert(p,q,i);insert(p,r,i);insert(q,r,i);
}
sort(s,s+top+1,cmp);
For(i,2,top)
if (s[i].mn==s[i-1].mn&&s[i].mx==s[i-1].mx) addedge(s[i].id,s[i-1].id);
dfs(1,0);
printf("%d\n",dia+1);
return 0;
}