算法1
我发现我的做法比较少见（就是比别人的都要复杂qaq），其他题解有更方便的做法。
我的想法是先计算出树的直径（2次dfs），求出dep数组（i节点往下走最长的深度），和maxn数组（i节点往上走最长的深度（注意这里有i节点可以先走到父亲再走到父亲节点的其他子节点等类似的情况））
之后求出树的直径的可行边（就是向下最长的长度加上向上最长的长度刚好等于直径的长度）（第三次dfs）
第四次dfs，可以发现如果对于dfs到的当前节点curr，与curr相连的边（包括父节点与子节点）如果有大于两条为可行边，就会出现有的边不是必须边的情况。
这里分两种情况讨论：
第一种情况：curr节点通过走这些边能到达最远的距离（对于curr的子节点就是最长的深度dep数组，对于curr的父节点就是往上走最长的深度maxn数组）全部相等
此时这些从这些边中选择任意两条都是直径，所以这些边都不是必须边
第二种情况：这些距离不相等。此时只可能有一个距离最大，其他的都相等。此时相等的那些边不是必须边。
对于不是必须边的边，给他们打上标记。如果它是curr与父节点之间的边，那么除了curr子树以外的边都不是必须边（curr往上的那些边都不是）。如果是curr与子节点的边，那么curr子树内的边都不是必须边
第五次dfs，扫描每一个节点，如果curr节点到子节点的边被标记往下，那么清空子节点的子树，如果有curr子节点中往上的边大于等于2条（dfs返回值为true也算），此时整棵树都要被清空，如果只有一条，就清空除了这个子节点以外的其他子树，以及curr往上的子树（这里让dfs的返回值为true）。
注意边的编号应该从2开始，这样a到b的边与b到a的边的编号可以由异或1得到。
于是这题我硬是写了200行代码。。。
我这个解法并不是最好的（特别麻烦），我讲的也不太清楚，大家就当做看着好玩吧。
C++ 代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n;
int Head[200001],To[400005],Next[400005],t1=1;
long long W[400005];
bool pd[400005];
void add(int a,int b,int c)
{
t1++;
Next[t1]=Head[a];
Head[a]=t1;
To[t1]=b;
W[t1]=c;
}
bool vis[200001];
int fa[200001];
long long dep[200001],maxn[200001];
int t[200001],c;
long long w[200001];
void dfs1(int curr)
{
vis[curr]=1;
for (int i=Head[curr];i;i=Next[i])
{
if (!vis[To[i]])
{
fa[To[i]]=curr;
dfs1(To[i]);
dep[curr]=max(dep[curr],dep[To[i]]+W[i]);
}
}
c=0;
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr) t[++c]=To[i],w[c]=W[i];
}
long long tem=0;
for (int i=1;i<=c;i++)
{
maxn[t[i]]=max(maxn[t[i]],tem+w[i]);
tem=max(tem,dep[t[i]]+w[i]);
}
tem=0;
for (int i=c;i>=1;i--)
{
maxn[t[i]]=max(maxn[t[i]],tem+w[i]);
tem=max(tem,dep[t[i]]+w[i]);
}
}
long long len;
void dfs2(int curr)
{
len=max(len,maxn[curr]+dep[curr]);
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
maxn[To[i]]=max(maxn[To[i]],maxn[curr]+W[i]);
dfs2(To[i]);
}
}
}
void dfs3(int curr)
{
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
if (maxn[To[i]]+dep[To[i]]==len) pd[i]=pd[i^1]=1;
dfs3(To[i]);
}
}
}
bool delu[400005],deld[400005];
void dfs4(int curr,int id)
{
c=0;
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
if (pd[i]) t[++c]=i;
}
}
if (pd[id]) t[++c]=id;
if (c>2)
{
long long tem=0;
for (int i=1;i<=c;i++)
{
if (t[i]==id) tem=max(tem,maxn[curr]);
else tem=max(tem,dep[To[t[i]]]+W[t[i]]);
}
int cnt=0;
for (int i=1;i<=c;i++)
{
if (t[i]==id&&maxn[curr]==tem) cnt++;
if (t[i]!=id&&dep[To[t[i]]]+W[t[i]]==tem) cnt++;
}
if (cnt==c)
{
for (int i=1;i<=c;i++)
{
if (t[i]==id) delu[t[i]]=delu[t[i]^1]=1;
else deld[t[i]]=deld[t[i]^1]=1;
}
}
else
{
for (int i=1;i<=c;i++)
{
if ((t[i]==id&&maxn[curr]==tem)||(t[i]!=id&&dep[To[t[i]]]+W[t[i]]==tem)) continue;
if (t[i]==id) delu[t[i]]=delu[t[i]^1]=1;
else deld[t[i]]=deld[t[i]^1]=1;
}
}
}
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
dfs4(To[i],i);
}
}
}
bool del[200001];
void dele(int curr)
{
if (del[curr]) return;
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
pd[i]=pd[i^1]=0;
dele(To[i]);
}
}
del[curr]=1;
}
bool dfs5(int curr)
{
int cnt=0,tem;
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr)
{
if (deld[i])
{
pd[i]=pd[i^1]=0;
dele(To[i]);
}
if (dfs5(To[i])||delu[i])//注意顺序不能反了，保证一定访问To[i]
{
pd[i]=pd[i^1]=0; //注意这一行不要漏了，确保删完所有的边
cnt++,tem=i;
}
}
}
if (cnt>=2) dele(1);
else if (cnt==1)
{
for (int i=Head[curr];i;i=Next[i])
{
if (fa[To[i]]==curr&&tem!=i)
{
pd[i]=pd[i^1]=0;
dele(To[i]);
}
}
return true;
}
return false;
}
int main()
{
scanf("%d",&n);
for (int i=1,a,b,c;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c); add(b,a,c);
}
dfs1(1);
dfs2(1);
dfs3(1);
dfs4(1,0);
dfs5(1);
int ans=0;
for (int i=1;i<=t1;i++)
{
if (pd[i]) ans++;
}
printf("%lld\n%d\n",len,ans/2);
return 0;
}
