当前位置:网站首页>P4408 [NOI2003] 逃学的小孩(树的直径)
P4408 [NOI2003] 逃学的小孩(树的直径)
2022-07-05 00:02:00 【eva_can(not)survive】
[NOI2003] 逃学的小孩 - 洛谷https://www.luogu.com.cn/problem/P4408一道学习树的直径的好题。
题目要求最长的时间,说明答案应该是树的直径+max(起点离最近的朋友家的距离)
所以我们不仅仅要求树的直径,更要记录直径上的点,并遍历它们求最长延申距离。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;
int n, m;
int head[MAXN];
int nxt[MAXN];
int ver[MAXN];
ll cost[MAXN];
ll dis[MAXN];
int last[MAXN];
int cnt;
void add(int x, int y, ll c) {
ver[++cnt] = y;
nxt[cnt] = head[x];
cost[cnt] = c;
head[x] = cnt;
}
ll ans;
ll maxlen;
int recv, recu;
bool vis[MAXN];
void dfs(int p, ll rec, int fa) {
if (maxlen < rec)
maxlen = rec, recv = p;
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
// dis[v]=dis[p]+cost[i];
dfs(v, rec + cost[i], p);
}
}
void dfs1(int p, int fa) {
last[p] = fa;
if (maxlen < dis[p])
maxlen = dis[p], recu = p;
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dis[v] = dis[p] + cost[i];
dfs1(v, p);
}
}
ll mxx[MAXN];
ll mx;
void dfs2(int p, ll rec, int fa) {
mx = max(mx, rec);
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (vis[v] || v == fa)
continue;
dfs2(v, rec + cost[i], p);
}
}
int main() {
scanf("%d %d", &n, &m);
int x, y;
ll c;
for (int i = 1; i <= m; i++) {
scanf("%d %d %lld", &x, &y, &c);
add(x, y, c);
add(y, x, c);
}
dfs(1, 0, 0);
maxlen = 0;
dfs1(recv, 0);
ll tmp = 0;
for (int i = recu; i; i = last[i]) {
vis[i] = 1;
}
for (int i = recu; i; i = last[i]) {
mx = 0;
dfs2(i, 0, 0);
mxx[i] = mx;
}
mx = 0;
for (int i = recu; i; i = last[i]) {
tmp = min(dis[i], maxlen - dis[i]);
mx = max(mx, mxx[i] + tmp);
}
printf("%lld\n", mx + maxlen);
return 0;
}
边栏推荐
- 机器人强化学习——Learning Synergies between Pushing and Grasping with Self-supervised DRL (2018)
- 高配笔记本使用CAD搬砖时卡死解决记录
- Power operation and maintenance cloud platform: open the new mode of "unattended and few people on duty" of power system
- Mit-6.824-lab4b-2022 (10000 word idea explanation - code construction)
- Selected cutting-edge technical articles of Bi Ren Academy of science and technology
- 45岁教授,她投出2个超级独角兽
- 「运维有小邓」域密码策略强化器
- MP advanced operation: time operation, SQL, querywapper, lambdaquerywapper (condition constructor) quick filter enumeration class
- ICML 2022 || 3DLinker: 用于分子链接设计的E(3)等变变分自编码器
- How to avoid arc generation—— Aafd fault arc detector solves the problem for you
猜你喜欢
Fast parsing intranet penetration helps enterprises quickly achieve collaborative office
端口映射和端口转发区别是什么
如何有效对直流列头柜进行监测
ECCV 2022 | Tencent Youtu proposed disco: the effect of saving small models in self supervised learning
Robot reinforcement learning synergies between pushing and grassing with self supervised DRL (2018)
同事的接口文档我每次看着就头大,毛病多多。。。
PMP certificate renewal process
[论文阅读] TUN-Det: A Novel Network for Thyroid Ultrasound Nodule Detection
【雅思阅读】王希伟阅读P4(matching2段落信息配对题【困难】)
【kotlin】第三天
随机推荐
Fast analysis -- easy to use intranet security software
How to save your code works quickly to better protect your labor achievements
Robot reinforcement learning synergies between pushing and grassing with self supervised DRL (2018)
In June, the list of winners of "Moli original author program" was announced! Invite you to talk about the domestic database
The input of uniapp is invalid except for numbers
[JS] - [sort related] - Notes
How to use fast parsing to make IOT cloud platform
机器人强化学习——Learning Synergies between Pushing and Grasping with Self-supervised DRL (2018)
如何避免电弧产生?—— AAFD故障电弧探测器为您解决
业务场景功能的继续修改
Mit-6.824-lab4b-2022 (10000 word idea explanation - code construction)
How to do the project of computer remote company in foreign Internet?
微服务(Microservice)那点事儿
Introduction to ACM combination counting
QT addition calculator (simple case)
蓝天NH55系列笔记本内存读写速度奇慢解决过程记录
Summary of week 22-07-02
Réseau graphique: Qu'est - ce que le Protocole d'équilibrage de charge de passerelle glbp?
Jar batch management gadget
Design of emergency lighting evacuation indication system for urban rail transit station