当前位置:网站首页>P3304 [sdoi2013] diameter (diameter of tree)
P3304 [sdoi2013] diameter (diameter of tree)
2022-07-05 00:05:00 【eva_ can(not)survive】
[SDOI2013] The diameter of - Luogu https://www.luogu.com.cn/problem/P3304 Run first on this topic dfs Find any diameter , And record the path and the endpoints at both ends , First enumerate each point on the diameter starting from the left end point , Record the maximum path value of other paths at this point ( A road with a different diameter ), Then start to find out whether these maximum path values are equal to the original one ( It's equivalent to whether the forked road is as long as the original ), Then find the point , Then judge the distance from the right endpoint from this point ( Same as above )
The painting is very abstract , I hope it will help you understand
#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;
int ver[MAXN];
int head[MAXN];
int nxt[MAXN];
ll cost[MAXN];
int last[MAXN];
int nxxt[MAXN];
ll dis[MAXN], mmm[MAXN], op;
bool vis[MAXN];
int u, v;
int cnt;
void add(int x, int y, ll c) {
ver[++cnt] = y;
cost[cnt] = c;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs1(int o, ll p, int q) {
if (p > op)
op = p, u = o;
for (int i = head[o]; i; i = nxt[i]) {
if (ver[i] == q)
continue;
dfs1(ver[i], p + cost[i], o);
}
}
void dfs2(int o, ll p, int q) {
last[o] = q;
dis[o] = p;
if (p > op)
op = p, v = o;
for (int i = head[o]; i; i = nxt[i]) {
if (ver[i] == q)
continue;
dfs2(ver[i], p + cost[i], o);
}
}
void dfs(int o, ll p, int q) {
if (p > op)
op = p;
for (int i = head[o]; i; i = nxt[i]) {
if (vis[ver[i]] || ver[i] == q)
continue;
dfs(ver[i], p + cost[i], o);
}
}
int main() {
scanf("%d", &n);
int x, y;
ll c;
for (int i = 1; i <= n - 1; i++) {
scanf("%d %d %lld", &x, &y, &c);
add(x, y, c);
add(y, x, c);
}
dfs1(1, 0, 0);
op = 0;
dfs2(u, 0, 0);
ll distance = dis[v];
printf("%lld\n", distance);
for (int i = v; i; i = last[i]) {
vis[i] = 1;
}
for (int i = v; i; i = last[i]) {
op = 0;
dfs(i, 0, 0);
mmm[i] = op;
}
for (int i = last[v], j = v; i; i = last[i]) {
nxxt[i] = j, j = i;
}
int tmp;
for (int i = u; i; i = nxxt[i]) {
if (dis[v] - dis[i] == mmm[i]) {
tmp = i;
break;
}
}
int ans = 0;
for (int i = tmp; i; i = last[i]) {
if (dis[i] == mmm[i])
break;
ans++;
}
printf("%d\n", ans);
return 0;
}
边栏推荐
- 实战模拟│JWT 登录认证
- IELTS examination process, what to pay attention to and how to review?
- How to apply for PMP project management certification examination?
- Fast analysis -- easy to use intranet security software
- 人脸识别5- insight-face-paddle-代码实战笔记
- uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
- XML的解析
- 电力运维云平台:开启电力系统“无人值班、少人值守”新模式
- js正则表达式之中文验证(转)
- P4281 [AHOI2008]紧急集合 / 聚会(LCA)
猜你喜欢
abc 258 G - Triangle(bitset)
uniapp 除了数字,其他输入无效
【路径规划】RRT增加动力模型进行轨迹规划
The input of uniapp is invalid except for numbers
Application of fire fighting system based on 3D GIS platform
He worked as a foreign lead and paid off all the housing loans in a year
Specification for fs4061a boost 8.4v charging IC chip and fs4061b boost 12.6V charging IC chip datasheet
Parsing of XML
香港珠宝大亨,22亿“抄底”佐丹奴
端口映射和端口转发区别是什么
随机推荐
Application of multi loop instrument in base station "switching to direct"
Ap8022 switching power supply small household appliances ACDC chip offline switching power supply IC
Date time type and format in MySQL
Specification for fs4061a boost 8.4v charging IC chip and fs4061b boost 12.6V charging IC chip datasheet
Power operation and maintenance cloud platform: open the new mode of "unattended and few people on duty" of power system
用快解析内网穿透实现零成本自建网站
Illustrated network: what is gateway load balancing protocol GLBP?
[kotlin] the third day
Hologres Query管理及超时处理
P3304 [SDOI2013]直径(树的直径)
如何报考PMP项目管理认证考试?
Actual combat simulation │ JWT login authentication
【雅思阅读】王希伟阅读P3(Heading)
海思3559万能平台搭建:YUV422的踩坑记录
Solution record of jamming when using CAD to move bricks in high configuration notebook
[paper reading] cavemix: a simple data augmentation method for brain vision segmentation
OSEK standard ISO_ 17356 summary introduction
Go pit - no required module provides Package: go. Mod file not found in current directory or any parent
Réseau graphique: Qu'est - ce que le Protocole d'équilibrage de charge de passerelle glbp?
Pytoch --- use pytoch to realize linknet for semantic segmentation