当前位置:网站首页>P4408 [noi2003] truant children (tree diameter)
P4408 [noi2003] truant children (tree diameter)
2022-07-05 00:05:00 【eva_ can(not)survive】
[NOI2003] Kids playing truant - Luogu https://www.luogu.com.cn/problem/P4408 A good question for learning the diameter of trees .
The longest time required for the topic , Explain that the answer should be the diameter of the tree +max( The distance from the starting point to the nearest friend's home )
So we don't just ask for the diameter of the tree , Record the point on the diameter , And traverse them to find the longest extension distance .
#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;
}
边栏推荐
- IT转测试岗,从迷茫到坚定我究竟付出了什么?
- Basic points of the game setup of the points mall
- Hologres Query管理及超时处理
- 城市轨道交通站应急照明疏散指示系统设计
- [paper reading] cavemix: a simple data augmentation method for brain vision segmentation
- The input of uniapp is invalid except for numbers
- 【雅思阅读】王希伟阅读P4(matching2段落信息配对题【困难】)
- Microservice
- 端口映射和端口转发区别是什么
- Five papers recommended for the new development of convolutional neural network in deep learning
猜你喜欢
In June, the list of winners of "Moli original author program" was announced! Invite you to talk about the domestic database
如何避免电弧产生?—— AAFD故障电弧探测器为您解决
45 year old professor, she threw two super unicorns
IELTS examination process, what to pay attention to and how to review?
"Xiaodeng" domain password policy enhancer in operation and maintenance
French scholars: the explicability of counter attack under optimal transmission theory
Continuous modification of business scenario functions
It's too convenient. You can complete the code release and approval by nailing it!
Summer challenge brings you to play harmoniyos multi terminal piano performance
abc 258 G - Triangle(bitset)
随机推荐
Verilog tutorial (11) initial block in Verilog
Hong Kong Jewelry tycoon, 2.2 billion "bargain hunting" Giordano
Application of fire fighting system based on 3D GIS platform
[IELTS reading] Wang Xiwei reading P4 (matching1)
Go step on the pit - no required module provides package: go mod file not found in current directory or any parent
香港珠宝大亨,22亿“抄底”佐丹奴
端口映射和端口转发区别是什么
Hash table, hash function, bloom filter, consistency hash
Pytoch --- use pytoch to realize linknet for semantic segmentation
Is it safe to open an account in the College of Finance and economics? How to open an account?
用快解析内网穿透实现零成本自建网站
电力运维云平台:开启电力系统“无人值班、少人值守”新模式
A new method for analyzing the trend chart of London Silver
Combien de temps faut - il pour obtenir un certificat PMP?
uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
人脸识别5- insight-face-paddle-代码实战笔记
It's too convenient. You can complete the code release and approval by nailing it!
基本放大电路的学习
IT转测试岗,从迷茫到坚定我究竟付出了什么?
Using the uniapp rich text editor