博客
关于我
2019牛客国庆集训派对day4H题
阅读量:653 次
发布时间:2019-03-15

本文共 995 字,大约阅读时间需要 3 分钟。

新建一棵树,边权等于原树中(u, v)的唯一路径距离,目标是最大化新树的总成本。

首先,确定原树的直径。直径是指树中延伸最远的简单路径。寻找直径的两个端点可以使用三次DFS:

  • 从任意节点出发,进行DFS,记录每个节点到起点的最远距离。
  • 在第一步中的最远节点作为起点,进行DFS,记录每个节点到该节点的最远距离。
  • 这两个最远节点即为原树的直径端点。
  • 接下来,计算直径端点到其它所有节点的距离之和,即为新树的最大成本。

    最佳做法是三次DFS:

    #include 
    #include
    using namespace std;vector
    > G[maxn];vector
    visited;ll dist = -1e18;int point;ll res[maxn];void dfs(int x, bool update, int index) { if (update) { if (G[x].size() > dist) dist = G[x].size(); point = x; } for (int v : G[x]) { if (!visited[v]) { visited[v] = true; if (!update) res[index][v] = res[index][x] + G[x][v]; else if (dist <= res[index][x] + G[x][v]) { res[index][v] = res[index][x] + G[x][v]; dist = res[index][v]; } dfs(v, update, index); } }}

    需要注意的是,优化代码时应保留所有必要的变量和结构,确保程序正确工作。完成三次DFS后,点point即为终点,dist记录原树的直径长度。

    最终,计算步骤即为从两个端点出发的总距离和,得到为新树的最大成本。

    转载地址:http://pzfmz.baihongyu.com/

    你可能感兴趣的文章
    Python中进行特征重要性分析的9个常用方法
    查看>>
    Python中通过MyQR生成gif动图二维码
    查看>>
    Python中通过PyPDF2实现PDF加密
    查看>>
    Python中通过PyPDF2实现PDF合并
    查看>>
    Python中通过PyPDF2实现PDF拆分
    查看>>
    Python中通过PyPDF2实现PDF添加水印
    查看>>
    Python中遍历字符串和字典
    查看>>
    Python中重复导入相同的库会发生问题吗?-ChatGPT4o作答
    查看>>
    python中非0即True,0即False
    查看>>
    python中高阶函数与装饰器(2)
    查看>>
    python之celery使用详解一
    查看>>
    python之glob
    查看>>
    python之Ipython的安装使用以及指定python版本号
    查看>>
    Python之json模块
    查看>>
    Python之lambda函数
    查看>>
    Python之matplotlib学习(一)
    查看>>
    python之Matplotlib详细分析(附代码)
    查看>>
    python之numpy详细分析(附代码)
    查看>>
    Python之OS模块进程管理介绍--os.fork()
    查看>>
    python之pandas详细分析(附代码)
    查看>>