首先求一遍直径，记起点为，终点为
所有可行边均在直径上（废话）
考虑直径上某个点，求出它不经过直径的能访问的最远距离，记为
复杂度显然是的
从到，依次遍历直径上所有点
- 若，则到之间所有的边均不是必须经过的
- 若，则到之间所有的边均不是必须经过的
需要注意的是，有些算法在遇到第二种情况时需要及时退出1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
using namespace std;
const int N=200050;
int n,st,ed,fa[N],col[N],ans=0;
LL d[N],len;
vector<int> e[N],g[N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int val)
{
e[u].push_back(v);
g[u].push_back(val);
}
void find(int o,int pre,int &x)
{
if (o==pre) d[o]=0,fa[o]=0;
if (!x||d[o]>d[x]) x=o;
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (to!=pre)
{
fa[to]=o;
d[to]=d[o]+g[o][i];
find(to,o,x);
}
}
}
LL dfs(int o)
{
LL ret=0;
col[o]=1;
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (!col[to]) ret=max(ret,dfs(to)+g[o][i]);
}
return ret;
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
int val=read();
add(u,v,val);
add(v,u,val);
}
find(n,n,ed);
find(ed,ed,st);
printf("%lld\n",len=d[st]);
for(int i=st;i;i=fa[i]) col[i]=1;
for(int f=0,i=st;i&&!f;i=fa[i])
for(int j=0;!f&&j<e[i].size();j++)
{
int to=e[i][j];
if (!col[to])
{
LL x=dfs(to)+g[i][j];
if (x==len-d[i]) st=i;
if (x==d[i]) ed=i,f=1;
}
}
for(int i=st;i!=ed;i=fa[i]) ans++;
printf("%d\n",ans);
return 0;
}