HDU 2196 Computer(求树上每一个节点到其他点的最远距离)
2024-08-31 13:40:50
解题思路:
求出树的直径的两个端点。则树上每一个节点到其它点的最远距离一定是到这两个端点的距离中最长的那一个。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#define LL long long
using namespace std;
const int MAXN = 100000 + 10;
struct Edge
{
int to, next, w;
}edge[2 * MAXN];
int tot;
int head[MAXN];
int dis[MAXN];
int N, M;
int D[MAXN];
void init()
{
tot = 0;
memset(head, -1, sizeof(head));
memset(D, 0, sizeof(D));
}
void addedge(int u, int v, int w)
{
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].w = w;
head[u] = tot++;
}
int dfs(int u, int pre = -1)
{
int ans = u;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v = edge[i].to;
if(v == pre) continue;
dis[v] = dis[u] + edge[i].w;
int dv = dfs(v, u);
if(dis[ans] < dis[dv]) ans = dv;
}
return ans;
}
int solve(int u)
{
dis[u] = 0;
u = dfs(u);
dis[u] = 0;
int v = dfs(u);
for(int i=1;i<=N;i++) D[i] = max(D[i], dis[i]);
dis[v] = 0;
dfs(v);
for(int i=1;i<=N;i++) D[i] = max(D[i], dis[i]);
for(int i=1;i<=N;i++) cout << D[i] << endl;
}
int main()
{
while(scanf("%d", &N)!=EOF)
{
int v, w;
init();
for(int i=2;i<=N;i++)
{
scanf("%d%d", &v, &w);
addedge(i, v, w);
addedge(v, i, w);
}
solve(1);
}
return 0;
}
最新文章
- CF444C. DZY Loves Colors[线段树 区间]
- 运用node的文件系统模块批量修改文件名
- xml/map转换器,递归设计思路
- 弄个知乎的粒子动态背景_实践particles.js
- android更换工具链
- Servlet的配置
- php 对多维数组排序array_multisort
- 【转】Mysql中varchar存放中文与英文所占字节异同
- ubuntu挂载其他分区到/home下,将当前分区内容替换
- Tian Ji -- The Horse Racing
- springMVC中文乱码问题解决
- 记一次小型生产事故 | BeyondComper跨编码方式复制文件内容
- 非常好用的弹出层 layer,常用功能demo,快速上手!
- 如何在eclipse中添加ADT
- 卷积神经网络之VGG
- Keil相关问题
- sql语句实例练习
- 【CUDA】Win10 + VS2017新 CUDA 项目配置
- [LeetCode] 35. Search Insert Position_Easy tag: Binary Search
- python--selenium简单模拟百度搜索点击器
热门文章
- 线性回归(regression)
- python_for循环
- pytorch 1 torch_numpy, 对比
- CSS隐藏overflow默认滚动条同时保留滚动效果
- Maven学习总结(25)——Eclipse Maven Update 时JDK版本变更问题
- 洛谷 P2932 [USACO09JAN]地震造成的破坏Earthquake Damage
- [ReactVR] Add Lighting Using Light Components in React VR
- word2vec词向量训练及中文文本类似度计算
- Coding上部署Ghost博客
- C#高级编程五十八天----并行集合