AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 1078. 旅游规划

作者: 作者的头像   DriftingAE86 ,  2020-11-03 22:59:54 ,  阅读 22


0


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 200010, M = N * 2;
int h[N], ne[M], idx, e[M];
int n;
int d1[N], d2[N]; // d1[i],d2[i] 表示以 i 为根节点,向下遍历的最大路径值 和 次大路径值
int up[N]; // up[i]:在一个树中,从i号节点向上遍历的路径长度最大值。应当等于:从父节点u出发且不经过i的最大路径值
int p1[N]; // p[i] 表示与节点i连接的所有子树中,最大的子树的根节点序号。
int maxd;

void init() {
    idx = 0;
    memset(h, -1, sizeof h);
}

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs_down(int s, int fa) {
    d1[s] += 1;
    d2[s] += 1;

    for (int i = h[s]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {

            dfs_down(j, s);
            int distance = d1[j] + 1;
            if (distance > d1[s]) {
                d2[s] = d1[s], d1[s] = distance;
                p1[s] = j; // 记录以当前节点为根节点的、最大子树的根节点为哪一个
            } else {
                d2[s] = max(d2[s], distance);
            }

        }
    }

    maxd = max(maxd, d1[s] + d2[s]);

}

void dfs_up(int s, int fa) {
    for (int i = h[s]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) { // 因为邻接表存储的特点,防止节点s的子节点j在dfs时又遍历回j的父节点s,这样就产生回路,死循环了。

            up[j] = up[s] + 1;
            if (d1[s] + 1 > up[j] && p1[s] != j) {
                up[j] = d1[s] + 1;
            }
            if (p1[s] == j) {
                up[j] = max(up[j], d2[s] + 1);
            }

            // if (p1[s] == j) up[j] = max(up[j], d2[s] + 1);
            // else up[j] = max(up[j], d1[s] + 1);

            dfs_up(j, s);
        }

    }
}

int main()
{
    init();
    scanf("%d", &n);
    int u, v;
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }

    // 这里第一次调用时,第一个参数0的含义表示我们假设0号点为整个树的根节点。
    dfs_down(0, -1); // 第一遍DFS求得f[i]表示树中,树根为i的子树的最大路径值

    dfs_up(0, -1);

    // printf("%d\n", maxd);

    for (int i = 0; i < n; ++i) {
        int d[3] = {d1[i], d2[i], up[i]};
        sort(d, d + 3);
        if (d[1] + d[2] == maxd)
            printf("%d\n", i);
    }


}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息