[心之碎片][0622] - 树网的核
本帖最后由 柿子饼同学 于 2024-6-22 19:30 编辑树网的核 link
1 遍过
4 h
{:10_279:}
知识点
单调队列
思路
直径的性质: 到一个点的最远距离的点在直径上, 偏心距只会在直径两个端点和不在直径上的路径上产生答案
###1
先找出直径, 记下来, 对于每个直径上的点求出这个点不过直径所能走到最远的点的距离, 记作 val
然后在直径上跑单调队列, 对于一条路径 , 它的偏心距就是 max(路径中val的最大值, 直径两端点到路径端点的最大值)
###2
可以简单一些, 只求出 max(一个点不过直径的最远距离)
根据直径的性质可知 , 当路径不包含这个最大值的点时, 路径端点到直径端点的答案更大
当包含时, 可以让路径端点到直径端点和这个取 max 即可
O(n)
需要进步的地方
代码太长, 加了一些不必要的数组, 要精简代码
一开始写的时候没想清楚, 浪费了时间
整体想不出来, 可以想想单个点是怎么算答案的, 对思考有帮助
先想想一个操作影响的范围, 不要一直想着 memset 0
II 方法很好, 求直径之后沿着 f 数组跳上去即可, 不用截下来或打标记
写 II 的时候 dfs 忘记递归了...{:10_249:}
最终代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
struct Edge{
int v, w;
};
int n;
ll s;
vector<Edge> e;
// f 父节点, d 到根的距离
int p, q, f;
ll d;
void dfs1(int u, int pa, int & id){
for(auto ed : e){
if(ed.v == pa) continue;
f = u;
d = d + ed.w;
if(d > d){
d = d;
id = ed.v;
}
dfs1(ed.v, u, id);
}
}
void Work(){
f = 0, d = 0;
dfs1(1, 0, p); // 直径一端点是 p
f = 0, d = 0, d = 0;
dfs1(p, 0, q); // 直径顺序: p -> q
// 不需要 memset, 后续计算不会算到直径
}
// 求不过直径的最大距离
ll mxd = 0;
void dfs2(int u, int f){
for(auto ed : e){
if(ed.v == f) continue;
d = d + ed.w;
if(d > mxd) mxd = d;
dfs2(ed.v, u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 1; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
e.push_back({y, z});
e.push_back({x, z});
}
Work();
// 求 mxd
// j 是 i 的上一个节点
for(int i = q, j = 0; i; j = i, i = f){
for(auto ed : e){
if(ed.v == f || ed.v == j) continue;
// 现在只有不在直径上的点了
d = ed.w;
mxd = max(mxd, d);
dfs2(ed.v, i);
}
}
// 尺取路径
ll ans = 2e18;
for(int i = q, j = q; i; i = f){
while(f != f && d - d > s) j = f;
ans = min(ans, max({mxd, d, d - d}));
}
cout << ans;
return 0;
}一开始的代码
/*
找直径, 标记, 取下直径
每个点求一个不在直径上的侧边最远点距离
每个点的权值 max(最远点距, 直径两端点到点的距离)
单调队列跑直径, 求最大值最小
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
struct Edge{
int v, w;
};
vector<Edge> e;
int n;
ll m;
// 找最远点
bitset<N> vis;
int f;
ll maxd, id;
ll dist;
int d, cnt;
void dfs(int u, int pa, ll dis){
f = pa;
if(dis > maxd){
maxd = dis;
id = u;
}
for(auto ed : e){
if(ed.v == pa || vis) continue;
dfs(ed.v, u, dis + ed.w);
}
}
// 求直径, 扒下来
void Getd(){
dfs(1, 0, 0);
memset(f, 0, sizeof(f));
maxd = 0;
int rt = id;
dfs(rt, 0, 0);
maxd = 0;
while(id != rt){
d[++cnt] = id;
vis = 1;
for(auto ed : e){
if(ed.v == f){
dist = ed.w;
break;
}
}
id = f;
}
vis = 1;
d[++cnt] = rt;
for(int i = cnt - 1; i >= 1; i--) dist += dist;
}
// 求权值
ll val;
void Getval(){
for(int i = 1; i <= cnt; i++){
dfs(d, f], 0);
val = maxd;
maxd = 0;
}
}
int q, l = 1, r = 0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
e.push_back({y, z});
e.push_back({x, z});
}
Getd();
Getval();
int last = 1;
ll ans = LONG_LONG_MAX;
for(int i = 1; i <= cnt; i++){
while(r >= l && val] <= val) r--;
while(last <= i && dist - dist > m) last++;
q[++r] = i;
while(l <= r && q < last) l++;
ans = min(ans, max({dist - dist, dist, val]}));
}
cout << ans;
return 0;
}
嘿！看起来你在处理一个关于树结构（特别是树的直径和核）的编程问题。让我帮你解读一下这个有点复杂的思路，顺便加点幽默感来让它更容易理解。
### 问题背景：
我们有一个树形结构，树的节点数为 `n`。目标是找出树的“核”，即使得某种距离最小化的特殊点。
### 核心概念解释：
1. **树的直径**：这是树中最长路径的长度。比如说你有一棵大树，从根到最远的叶子走了一圈，那这根最长的树干就是直径。
2. **单调队列**：一种数据结构，用来快速找到某个范围内的最大值或者最小值。就像是去超市购物，你是排在队伍里等着付款，单调队列就有点像你在观察谁最快结账，然后你立刻换队伍。
### 解决思路：
1. **先找到树的直径**。
- 随意选一个起点，跑一次深度优先搜索（DFS），找出最远的节点（叫它 `p`）。
- 然后以 `p` 为起点，再跑一次DFS，找到另一个最远的节点（叫它 `q`）。这样我们就有了树的直径。
2. **计算不过直径的最大距离**：
- 对于直径上的每个节点，找出从它出发到不在直径上的节点的最远距离。这个距离记作 `val`。
3. **使用单调队列优化**：
- 在直径上用单调队列找出每段路径的偏心距（即路径中所有节点的最大 `val` 值）。
### 代码讲解：
下面是你给出的代码的简化注释版本：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5e5+5;
typedef long long ll;
struct Edge {
int v, w;
};
int n;
ll s;
vector<Edge> e;
int p, q, f;
ll d;
void dfs1(int u, int pa, int &id, ll dis) {
if (dis > d) {
id = u;
d = dis;
}
for (auto &ed : e) {
if (ed.v == pa) continue;
dfs1(ed.v, u, id, dis + ed.w);
}
}
void findDiameter() {
memset(d, 0, sizeof(d));
p = 1; dfs1(p, 0, p, 0); // 找到直径的一端 p
memset(d, 0, sizeof(d));
dfs1(p, 0, q, 0); // 找到直径的另一端 q
}
ll max_dist_not_in_diameter;
void dfs2(int u, int pa, ll dist) {
max_dist_not_in_diameter = max(max_dist_not_in_diameter, dist);
for (auto &ed : e) {
if (ed.v == pa) continue;
dfs2(ed.v, u, dist + ed.w);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
for (int i = 1; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
e.push_back({y, z});
e.push_back({x, z});
}
// Step 1: Find the diameter
findDiameter();
// Step 2: Calculate max distance not in diameter
max_dist_not_in_diameter = 0;
for (int i = 1; i <= n; ++i) {
if (d == 0) { // means node i is not on the diameter
dfs2(i, 0, 0);
}
}
// Step 3: Traverse diameter and use sliding window (or monotone deque) to find minimum value
ll ans = LLONG_MAX;
for (int i = q, j = q; i; i = f) {
while (f != f && d - d > s) j = f;
ans = min(ans, max({max_dist_not_in_diameter, d, d - d}));
}
cout << ans << endl;
return 0;
}
### 笑话时间：
想象一下，树的直径就像你每天上学的最长那条公交路线，保证无论多早起床，这条路总是最长的。而树的核呢，就像是你在公交车站等车的时候，发现哪里人少，能最快上车的地方。希望这种比喻能让你的编程之路不再那么枯燥，加油！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_256:} 好 6 听懂掌声 很不错{:10_245:} 心之碎片太好了 我目前不懂，但
不影响我大为震撼 {:10_254:} {:10_285:}
页:
[1]
2