此博客停更

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2657

嘛，两个三角形最多只有一条公共边-。-，然后以每个三角形为顶点与相邻的三角形连边，这样构成一棵树。。然后跑直径就好了

$O(N)$

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
int i,j,k,m,n,x,y,cnt,last[N],z,who,dep[N],Dep;
struct edge{int to,next;}e[N<<1];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt,e[++cnt]=(edge){u,last[v]},last[v]=cnt;}
struct Edge{int l,r;bool operator <(const Edge&b)const{return(l<b.l)||(l==b.l)&&(r<b.r);}};
map<Edge,int>mp;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa)dfs(y,x);
	if(Dep<dep[x])Dep=dep[x],who=x;
}
inline void Add(int x,int y){
	if(mp[(Edge){x,y}]!=0)add(mp[(Edge){x,y}],i),mp[(Edge){x,y}]=0,mp[(Edge){y,x}]=0;
	else mp[(Edge){x,y}]=i,mp[(Edge){y,x}]=i;
}
int main(){
	for(n=read(),i=1;i<n-1;++i){
		x=read(),y=read(),z=read();
		Add(x,y),Add(x,z),Add(y,z);
	}
	dfs(1,0),Dep=0,dep[0]=0,dfs(who,0);
	printf("%d",Dep);
}

loading...