YBTOJ 5.4例3 最长距离 题解

挂大分！！！！！！
1.一定要看清提干有没有多测
2.多测不清空 爆零两行泪
3.同时线性更新最大值和次大值时记得最大值更新要同时把旧的最大值给次大值

题解

首先可以想到一个最暴力的暴力 ： 对于每一个点 暴力枚举所有的点跑LCA 复杂度 \(O(n^2logn)\) 显然会炸
然后就有一个优化一点的暴力 ：显然有可能成为最长距离的结点一定是叶节点 所以暴力枚举所有叶节点就行 但是显然复杂度没啥大优化

然后再想想 发现对于每个点 所枚举的叶节点无非就两类：一类在它的子树内 一类不在
在子树内的结点可以用一个显而易见的树形dp解决 来看不在子树内的点
不难发现 对于不在子树内的点 显然当前点要跳到某个祖先 然后再下去到这个祖先内的最远点

（说句题外话 有这个就可以写一个 \(O(n^2)\) 的暴力 即暴力跳祖先枚举最远点 我不知道能不能过（））

那么再往下想 就可以发现我们可以dp维护出这个点上面这些所有祖先的最大值然后进行转移
然后就可以 \(O(n)\) 了！！！

当然这里需要注意一些细节问题 因为跳祖先是要找一个折一下的路径 所以这个点本身不能在那个祖先结点的最远点所在的子树内
所以我们需要额外维护出每个节点向下能到达的次远点 然后针对这个情况进行转移

设 \(f[i][0/1/2]\) 表示编号为i的结点向下最远距离/向下次远距离/向上再折下去的最远距离
设 \(idx[i]\) 表示编号为i的结点的最远点所在的子树的根节点的编号
对于第一次dp 我们有：
\(f[i][0] = max(f[son[i]][0] + dis[i][son[i])\)
$f[i][1] = 次大值(f[son[i]][0] + dis[i][son[i]]) $

对于第二次dp 我们有：
\(f[son[i]][2] = max(f[i][0], f[i][2]) + dis[i][son[i]] (son[i] != idx[i])\)
\(f[son[i]][2] = max(f[i][1], f[i][2]) + dis[i][son[i]] (son[i] == idx[i])\)

完整代码如下：

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e4 + 0721;
int head[N], to[N], nxt[N], dis[N], cnt;
int idx[N];
ll f[N][3];
int n;

inline void cmb(int x, int y, int z) {
    to[++cnt] = y;
    dis[cnt] = z;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

void dfs1(int x) {
    ll maxn = 0;
    ll cmax = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        dfs1(y);
        ll val = f[y][0] + dis[i];
        if (val > maxn) {
        	cmax = maxn;
            idx[x] = y;
            maxn = val;
        } else if (val >= cmax) cmax = val;
    }
    f[x][0] = maxn;
    f[x][1] = cmax;
}

void dfs2(int x) {
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y == idx[x])
            f[y][2] = max(f[x][1], f[x][2]) + dis[i];
        else
            f[y][2] = max(f[x][0], f[x][2]) + dis[i];
        dfs2(y);
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 0;
        for (int i = 1; i <= n; ++i) head[i] = 0;
        for (int i = 1; i <= n; ++i) f[i][0] = f[i][2] = f[i][1] = 0;

        for (int i = 2; i <= n; ++i) {
            int fa, v;
            scanf("%d%d", &fa, &v);
            cmb(fa, i, v);
        }

        dfs1(1);
        dfs2(1);
//      for (int i = 1; i <= n; ++i) cout << i << " " << f[i][0] << " " << f[i][1] << " " << f[i][2] << endl;

        for (int i = 1; i <= n; ++i) printf("%lld\n", max(f[i][0], f[i][2]));
    }

    return 0;
}