题目描述

小 Q 最近学习了一些图论知识。

根据课本，有如下定义。

树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。

如果一棵树有 N个节点，可以证明其有且仅有 N−1条边。

路径：一棵树上，任意两个节点之间最多有一条简单路径。

我们用 dis(a,b)表示点 a 和点 b 的路径上各边长度之和。

称 dis(a,b) 为 a、b 两个节点间的距离。

直径：一棵树上，最长的路径为树的直径。

树的直径可能不是唯一的。

现在小 Q 想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

输入格式
第一行包含一个整数 N ，表示节点数。
接下来 N−1 行，每行三个整数 a,b,c，表示点 a 和点 b 之间有一条长度为 c 的无向边。

输出格式
共两行。

第一行一个整数，表示直径的长度。

第二行一个整数，表示被所有直径经过的边的数量。

数据范围
2≤N≤200000,点的编号从 1 开始。
c≤1e9

输入样例

6 
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

输出样例

1110
2

思路：
1.2次dfs求出直径，同时记录直径的路径
2.对直径上的点进行标记
3.假设现在已经求得了一条直径的具体路径。设其两端分别为x和y。
从一端枚举到另外一端，并用l和r维护相交的部分。
先看x到y的。
设当前的节点为u。如果（u和x的距离）（除去公共路径那段）==（u不过直径能达到的最大长度），
说明u这里是直径的分叉口，l=u
再看y到x的。
同样的道理，若（u和y的距离）==（u不过直径的最大长度），r=u
这样就确定了l和r，完成！

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=2*N;
int n,e[M],ne[M],h[N],w[M],idx,dist[N],pre[N],sum,id1,id2,l,r,d[N],s,ans;
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int x,int father,int distance)
{
    dist[x]=distance;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            pre[j]=x;//存储路径
            dfs(j,x,distance+w[i]);
        }   
    }
}
void dfs1(int x,int father,int distance)
{
    if(st[x]&&father!=-1)return;
    if(distance>ans)ans=distance; 
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father&&!st[j])
        {
            distance+=w[i];
            dfs1(j,x,distance);
            distance-=w[i];
        }   
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1,0);//找到一个最远点
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>sum)
        {
            sum=dist[i];
            id1=i;
        }
    }
    memset(dist,0,sizeof(dist));
    pre[id1]=0;sum=0;//pre[N]数组存储路径
    dfs(id1,-1,0);//从最远点开始dfs找到直径
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>sum)
        {
            sum=dist[i];
            id2=i;//最远点
        }
    }
    cout<<sum<<endl;
    int temp=id2;
    while(temp)//标记直径
    {
        st[temp]=true;
        d[pre[temp]]=d[temp]+1;
        temp=pre[temp];
    }
    temp=id2,l=id2,r=id1;//初始化
    //id1:起点 id2:终点
    while(temp)
    {
        ans=0;
        dfs1(temp,-1,0);//遍历直径上每个点,找到当前点的最远距离
        //目的：找到其他直径，及公共边和其他直径的分叉点
        if(ans==dist[temp])//起点
        {
            r=temp;
            break;
        }
        if(ans==dist[id2]-dist[temp])l=temp;//找到分叉点
        temp=pre[temp];
    }
    cout<<d[r]-d[l];
}