这道题用到了一个非常有用的引理，树的所有直径拥有相同的中点！NOI2013有个叫快餐店的题也可以用这个引理。
这里中点可能在一条边的内部。证明的话用反证法，大家自己一画就明白。
这样一来，随便找一条直径，如果中点在某条边内部，那么这条边毫无疑问是在所有直径上的，然后我们去掉这条边，在剩下的两棵有根树里分别找从根到叶子的最长路上哪些边是必须的，递归解决即可。这个子问题非常有用，我们在这里叫他RootLeafPath。
另一种情况是中点是某个顶点，这时我们以中点为根dfs,那么所有直径都经过根，怎么看哪些边是必须的呢？显然要挑两个根的儿子往下走，我们设f[x]表示从一个节点向下走的最大深度，并挑出根的儿子中f[x]+(根到x的边权)中前三大的，不妨设他们是a,b,c。分为三种情况|：(1)如果b>c,那么在a,b对应的子树里做RootLeafPath即可。
(2)如果a>b=c,那么只在a对应子树里做RootLeafPath即可。
(3)如果a=b=c，这时没有任何一条边是必须的，输出0。
```cpp
#include <stdio.h>
#include <queue>
using namespace std;
int const N=4e5+1;
struct node{
int x;
long long val;
friend bool operator <(node a, node b){
return a.val<b.val;
}
};
int n,tot,to[N],pre[N],last[N],fa[N],ans=0;
long long v[N],d[N],f[N];
priority_queue<node> h;
void add(int a, int b, int c){
to[++tot]=b;
pre[tot]=last[a];
last[a]=tot;
v[tot]=c;
}
void dfs(int x, int father, long long deep){
d[x]=deep;
fa[x]=father;
f[x]=0;
for (int i=last[x];i;i=pre[i])
if (to[i]!=father) {
dfs(to[i],x,d[x]+v[i]);
f[x]=max(f[x],f[to[i]]+v[i]);
}
}
void work(int x, int father, int deep){
dfs(x,father,deep);
while (true){
int y=0,cnt=0;
for (int i=last[x];i;i=pre[i])
if (to[i]!=father && f[x]==f[to[i]]+v[i]) y=to[i],cnt++;
if (cnt==0 || cnt>=2) break;
father=x;
x=y;
ans++;
}
}
int main(){
freopen("p3304.in","r",stdin);
scanf("%d",&n);
if (n==2){
printf("1");
return 0;
}
for (int i=1;i<=n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs(1,0,0);
int now=0;
for (int i=1;i<=n;i++)
if (d[i]>d[now]) now=i;
dfs(now,0,0);
now=0;
for (int i=1;i<=n;i++)
if (d[i]>d[now]) now=i;
long long L=d[now];
while (d[fa[now]]*2>=L) now=fa[now];
if (d[now]*2==L){
dfs(now,0,0);
for (int i=last[now];i;i=pre[i])
h.push((node){to[i],v[i]+f[to[i]]});
node a=h.top();
h.pop();
node b=h.top();
h.pop();
if (h.empty()){
ans+=2;
work(a.x,now,0);
work(b.x,now,0);
} else{
node c=h.top();
if (b.val>c.val){
ans+=2;
work(a.x,now,0);
work(b.x,now,0);
} else{
if (a.val>b.val){
ans++;
work(a.x,now,0);
}
}
}
}
else{
ans++;
work(now,fa[now],0);
work(fa[now],now,0);
}
printf("%lld\n",L);
printf("%d\n",ans);
return 0;
}
```