[心之碎片][0622] - 树网的核

柿子饼同学

树网的核 link
1 遍过
4 h


知识点
单调队列


思路
直径的性质: 到一个点的最远距离的点在直径上, 偏心距只会在直径两个端点和不在直径上的路径上产生答案
###1
先找出直径, 记下来, 对于每个直径上的点求出这个点不过直径所能走到最远的点的距离, 记作 val
然后在直径上跑单调队列, 对于一条路径 , 它的偏心距就是 max(路径中val的最大值, 直径两端点到路径端点的最大值)
###2
可以简单一些, 只求出 max(一个点不过直径的最远距离)
根据直径的性质可知 , 当路径不包含这个最大值的点时, 路径端点到直径端点的答案更大
当包含时, 可以让路径端点到直径端点和这个取 max 即可
O(n)


需要进步的地方
代码太长, 加了一些不必要的数组, 要精简代码
一开始写的时候没想清楚, 浪费了时间
整体想不出来, 可以想想单个点是怎么算答案的, 对思考有帮助
先想想一个操作影响的范围, 不要一直想着 memset 0
II 方法很好, 求直径之后沿着 f 数组跳上去即可, 不用截下来或打标记
写 II 的时候 dfs 忘记递归了...


最终代码

#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[N];

// f 父节点, d 到根的距离
int p, q, f[N];
ll d[N];

void dfs1(int u, int pa, int & id){
    for(auto ed : e[u]){
        if(ed.v == pa) continue;
        f[ed.v] = u;
        d[ed.v] = d[u] + ed.w;

        if(d[ed.v] > d[0]){
            d[0] = d[ed.v];
            id = ed.v;
        }

        dfs1(ed.v, u, id);
    }
}

void Work(){
    f[1] = 0, d[1] = 0;
    dfs1(1, 0, p); // 直径一端点是 p
    f[p] = 0, d[p] = 0, d[0] = 0;
    dfs1(p, 0, q); // 直径顺序: p -> q
    // 不需要 memset, 后续计算不会算到直径
}

// 求不过直径的最大距离
ll mxd = 0;

void dfs2(int u, int f){
    for(auto ed : e[u]){
        if(ed.v == f) continue;
        d[ed.v] = d[u] + ed.w;
        if(d[ed.v] > mxd) mxd = d[ed.v];
        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[x].push_back({y, z});
        e[y].push_back({x, z});
    }

    Work();
    
    // 求 mxd
    // j 是 i 的上一个节点
    for(int i = q, j = 0; i; j = i, i = f[i]){
        for(auto ed : e[i]){
            if(ed.v == f[i] || ed.v == j) continue;

            // 现在只有不在直径上的点了
            d[ed.v] = ed.w;
            mxd = max(mxd, d[ed.v]);
            dfs2(ed.v, i);
        }
    }

    // 尺取路径 [i, j]
    ll ans = 2e18;
    for(int i = q, j = q; i; i = f[i]){
        while(f[j] != f[i] && d[j] - d[i] > s) j = f[j];
        ans = min(ans, max({mxd, d[i], d[q] - d[j]}));
    }

    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[N];
int n;
ll m;

// 找最远点
bitset<N> vis;
int f[N];
ll maxd, id;
ll dist[N];
int d[N], cnt;

void dfs(int u, int pa, ll dis){
    f[u] = pa;
    if(dis > maxd){
        maxd = dis;
        id = u;
    }

    for(auto ed : e[u]){
        if(ed.v == pa || vis[ed.v]) 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[id] = 1;

        for(auto ed : e[id]){
            if(ed.v == f[id]){
                dist[cnt] = ed.w;
                break;
            }
        }
        id = f[id];
    }
    vis[rt] = 1;
    d[++cnt] = rt;
    for(int i = cnt - 1; i >= 1; i--) dist[i] += dist[i + 1];
}

// 求权值
ll val[N];

void Getval(){
    for(int i = 1; i <= cnt; i++){
        dfs(d[i], f[d[i]], 0);
        val[i] = maxd;
        maxd = 0;
    }
}

int q[N], 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[x].push_back({y, z});
        e[y].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[q[r]] <= val[i]) r--;
        while(last <= i && dist[last] - dist[i] > m) last++;
        q[++r] = i;
        while(l <= r && q[l] < last) l++;

        ans = min(ans, max({dist[1] - dist[last], dist[i], val[q[l]]}));
    }

    cout << ans;

    return 0;
}

FishC

嘿！看起来你在处理一个关于树结构（特别是树的直径和核）的编程问题。让我帮你解读一下这个有点复杂的思路，顺便加点幽默感来让它更容易理解。

### 问题背景：
我们有一个树形结构，树的节点数为 `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[N];
int p, q, f[N];
ll d[N];

void dfs1(int u, int pa, int &id, ll dis) {
    if (dis > d[id]) {
        id = u;
        d[id] = dis;
    }
    for (auto &ed : e[u]) {
        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[u]) {
        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[x].push_back({y, z});
        e[y].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[i] == 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[i]) {
        while (f[j] != f[q] && d[i] - d[j] > s) j = f[j];
        ans = min(ans, max({max_dist_not_in_diameter, d[i], d[q] - d[j]}));
    }

    cout << ans << endl;
    return 0;
}

### 笑话时间：
想象一下，树的直径就像你每天上学的最长那条公交路线，保证无论多早起床，这条路总是最长的。而树的核呢，就像是你在公交车站等车的时候，发现哪里人少，能最快上车的地方。希望这种比喻能让你的编程之路不再那么枯燥，加油！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

kiara_03

好

harryhan123

6

hhy2024

听懂掌声

简柠啦

很不错

thekfjie

心之碎片太好了

希儿的

我目前不懂，但
不影响我大为震撼

harryhan123

harryhan123