RT。
我看网上很多大佬说树上DP只能求出长度,没法求其他的内容……以及 P3629的高赞题解 也这么说……
但是我自己貌似写的时候发现树上DP貌似能顺带求出树上直径的每条边……?
// f是节点向子树的最长/次长链,g是节点最长/次长链的第一条边
int f[MAXN][2], g[MAXN][2], res, mx = -0x3F3F3F3F, ans;
void dp(int cur, int s)
{
for (int i = head[cur]; i; i = e[i].nxt)
{
if (e[i].v == s)
continue;
dp(e[i].v, cur);
if (f[cur][0] < f[e[i].v][0] + e[i].w)
{
f[cur][1] = f[cur][0];
g[cur][1] = g[cur][0];
f[cur][0] = f[e[i].v][0] + e[i].w;
g[cur][0] = i;
}
else if (f[cur][1] < f[e[i].v][0] + e[i].w)
{
f[cur][1] = f[e[i].v][0] + e[i].w;
g[cur][1] = i;
}
}
if (mx < f[cur][0] + f[cur][1])
{
mx = f[cur][0] + f[cur][1];
res = cur;
}
}
不知道是不是自己写错了……求大佬们指点迷津(逃)