Submit: 924 Solved: 585
[Submit][Status][Discuss]
Description
到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~
经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。
为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？
Input
每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数N，N的含义如题目所述。
接下来有N-2行，每行包含三个整数 p,q,r，表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。
Output
输出文件共包含1行，表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)
Sample Input
6
1 2 4
2 3 4
1 4 5
1 5 6
1 2 4
2 3 4
1 4 5
1 5 6
Sample Output
4
HINT
4<=N<=200000
Source
树 最长路
在凸多边形的两个顶点之间连一条线，问如何连可以使得这条线穿过的三角形最多。
把每个三角形当作一个节点，在有共同边的两个三角形之间连长度为1的边，最后发现形成一个树结构，那么求树上最长链就可以了。
↑凸多边形的性质使得这么做是正确的。
↑什么性质？不可描述。怎么证明？画几个图，“显然可知”
做这题最逗的是，测试的时候过了，交一发bzoj发现WA了。WTF？提交之前压缩了下代码长度，就把71行求端点语句的括号缩没了，还傻傻没发现，蛤蛤蛤蛤蛤。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<map> 9 using namespace std; 10 const int mxn=300010; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int v,nxt; 19 }e[mxn<<1]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v){ 22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct; 23 e[++mct].v=u;e[mct].nxt=hd[v];hd[v]=mct; 24 return; 25 } 26 struct tri{ 27 int c[4]; 28 }a[mxn]; 29 int n,cnt=0; 30 map<pair<int,int>,int>mp; 31 void extend(tri x){ 32 ++cnt; 33 if(mp[make_pair(x.c[1],x.c[2])]){ 34 add_edge(cnt,mp[make_pair(x.c[1],x.c[2])]); 35 } 36 else mp[make_pair(x.c[1],x.c[2])]=cnt; 37 38 if(mp[make_pair(x.c[2],x.c[3])]){ 39 add_edge(cnt,mp[make_pair(x.c[2],x.c[3])]); 40 } 41 else mp[make_pair(x.c[2],x.c[3])]=cnt; 42 43 if(mp[make_pair(x.c[1],x.c[3])]){ 44 add_edge(cnt,mp[make_pair(x.c[1],x.c[3])]); 45 } 46 else mp[make_pair(x.c[1],x.c[3])]=cnt; 47 return; 48 } 49 int dis[mxn]; 50 void DFS(int u,int fa){ 51 dis[u]=dis[fa]+1; 52 for(int i=hd[u];i;i=e[i].nxt){ 53 int v=e[i].v; 54 if(v==fa)continue; 55 DFS(v,u); 56 } 57 return; 58 } 59 int main(){ 60 // freopen("journey.in","r",stdin); 61 // freopen("journey.out","w",stdout); 62 int i,j; 63 n=read();int ed=n-2; 64 for(i=1;i<=ed;i++){ 65 a[i].c[1]=read();a[i].c[2]=read();a[i].c[3]=read(); 66 sort(a[i].c+1,a[i].c+4); 67 extend(a[i]); 68 } 69 DFS(1,0); 70 int ans=0,pos=1; 71 for(i=1;i<=cnt;i++)if(dis[i]>ans){ans=dis[i];pos=i;}; 72 DFS(pos,0); 73 for(i=1;i<=cnt;i++) if(dis[i]>ans){ans=dis[i];} 74 printf("%d ",ans); 75 return 0; 76 }