鱼C论坛

 找回密码
 立即注册
查看: 729|回复: 22

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

[复制链接]
回帖奖励 2 鱼币 回复本帖可获得 2 鱼币奖励! 每人限 1 次
发表于 2024-6-22 17:09:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 柿子饼同学 于 2024-6-22 19:30 编辑
树网的核 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;
}

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
小肥狼haoran + 5 + 5 + 3 牛皮先支持一波

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-6-22 17:10:41 | 显示全部楼层
嘿!看起来你在处理一个关于树结构(特别是树的直径和核)的编程问题。让我帮你解读一下这个有点复杂的思路,顺便加点幽默感来让它更容易理解。

### 问题背景:
我们有一个树形结构,树的节点数为 `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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:36:57 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:37:10 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:37:22 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:37:34 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:37:45 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:38:15 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:38:25 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:38:40 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2024-6-26 20:38:58 | 显示全部楼层

回帖奖励 +2 鱼币

提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-6-28 21:59:51 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-1 14:20:16 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-2 18:15:32 | 显示全部楼层

回帖奖励 +2 鱼币

6
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-3 19:08:14 | 显示全部楼层

回帖奖励 +2 鱼币

听懂掌声
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-6 23:11:00 | 显示全部楼层

回帖奖励 +2 鱼币

很不错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-9 11:30:52 | 显示全部楼层

回帖奖励 +2 鱼币

心之碎片太好了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-9 14:42:16 | 显示全部楼层

回帖奖励 +2 鱼币

我目前不懂,但
不影响我大为震撼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-12 18:26:30 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-12 18:27:13 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-10-12 17:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表