D53 树的直径 建图技巧+两次DFS P2610 [ZJOI2012] 旅游

// 树的直径 建图技巧+两次DFS O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int h[N],to[N<<1],ne[N<<1],idx;
void add(int a,int b){
  to[++idx]=b; ne[idx]=h[a]; h[a]=idx;
  to[++idx]=a; ne[idx]=h[b]; h[b]=idx;
}
int n,d[N],p,ans;
map<pair<int,int>,int> mp;

void dfs(int x,int f){
  if(d[x]>d[p]) p=x; //记录直径的端点
  for(int i=h[x];i;i=ne[i]){
    int y=to[i];
    if(y!=f){
      d[y]=d[x]+1;   //记录从根到y的距离
      dfs(y,x);
    }
  }
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>n;
  for(int i=1,p,q,r;i<=n-2;++i){ //枚举三角形的编号，编号做树的节点
    cin>>p>>q>>r;
    if(p>q) swap(p,q);
    if(p>r) swap(p,r);
    if(q>r) swap(q,r);          //三角形顶点{p,q,r}升序排列，免去判重
    if(!mp[{p,q}]) mp[{p,q}]=i; //若当前边未遍历，则用当前三角形的编号标记
    else add(i,mp[{p,q}]);      //若当前边已遍历，说明当前三角形与已遍历过的三角形相邻，则把两三角形的编号用树边相连
    if(!mp[{p,r}]) mp[{p,r}]=i;
    else add(i,mp[{p,r}]);
    if(!mp[{q,r}]) mp[{q,r}]=i;
    else add(i,mp[{q,r}]);
  }
  dfs(1,0); d[p]=0;
  dfs(p,0); ans=d[p]+1; //答案是直径上的点数=边数+1
  cout<<ans;
}