求问树上DP能求出直径上的每条边么?
  • 板块学术版
  • 楼主SBofGaySchool
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/11/25 11:21
  • 上次更新2023/11/5 07:22:54
查看原帖
求问树上DP能求出直径上的每条边么?
219978
SBofGaySchool楼主2020/11/25 11:21

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;
    }
}

不知道是不是自己写错了……求大佬们指点迷津(逃)

2020/11/25 11:21
加载中...