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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
神奇的加边+SPFA求最长链~
读懂题以后就没有什么好想的了……然而题意好难懂啊QAQ……原来是不能走黑边，只能走不是黑边的对角线……
因为问的是不是黑边的对角线最多能穿过多少城市，考虑到穿过一个城市相当于长度+1，相邻两个城市可以互相选择，所以我们对在相邻两个城市之间连边，边权是1，再在这棵树上跑最长路就可以了~
最长路怎么求？蠢蠢的我刚开始写了普通的SPFA，结果死循环……只要把SPFA中q.pop()后面的b[w[i]]=0去掉就可以了，这样可以限制每个点只加一次。但是这种做法只适用于这题中树的情况，使用需谨慎~
另外，这样加边是因为我想不出其他的加边方法了……实际上复杂度依赖于边的分散与否……原来还以为会被特殊情况卡掉，结果居然一遍A……2333所以就不改了~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;int n,p,q,r,fi[200001],w[400001],ne[400001],ans,now,cnt,dis[200001];
bool b[200001];
vector<int> a[200001],c[200001];int abs(int u)
{return u>0 ? u:-u;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;
}void dfs(int u)
{queue<int> q;ans=0;now=u;memset(b,0,sizeof(b));memset(dis,-1,sizeof(dis));q.push(u);b[u]=1;dis[u]=1;while(!q.empty()){int k=q.front();q.pop();for(int i=fi[k];i;i=ne[i])if(dis[w[i]]<dis[k]+1){dis[w[i]]=dis[k]+1;if(dis[w[i]]>ans) ans=dis[w[i]],now=w[i];if(!b[w[i]]){b[w[i]]=1;q.push(w[i]);}}}
}void kk(int u,int v,int num)
{if(abs(u-v)<=1) return;if(u>v) swap(u,v);int len=a[u].size(),flag=0;for(int i=0;i<len;i++)if(a[u][i]==v) add(c[u][i],num),flag=1;if(!flag) a[u].push_back(v),c[u].push_back(num);
}int main()
{scanf("%d",&n);for(int i=1;i<=n-2;i++){scanf("%d%d%d",&p,&q,&r);kk(p,q,i);kk(q,r,i);kk(p,r,i);}dfs(1);dfs(now);printf("%d\n",ans);return 0;
}