复赛二：赛道修建(track)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

// 常量定义
const int MAXN = 50005;            // 最大节点数
const int INF = 0x7fffffff;        // 无穷大，用于初始化右边界

// 使用邻接表存储树的边，vector中存储<pair<目标节点, 边权重>>
vector<vector<pair<int, int>>> adj(MAXN);

// 节点数和需要形成的赛道数
int n, m;

// DFS使用的数组
int dp[MAXN];            // dp[x]表示从节点x向上延伸的最长路径长度
int tag[MAXN];           // tag数组用于标记路径是否已被选中
int que[MAXN];           // que数组用于存储当前节点的所有部分路径长度
int tail;                // que数组的尾指针
int res;                 // 剩余需要形成的赛道数

//向邻接表中添加一条边, x 起始节点编号, y目标节点编号, z 边的权重（长度）。
 
inline void Addline(int x, int y, int z){
    adj[x].push_back(make_pair(y, z)); // 使用 push_back 添加从x到y的边
    adj[y].push_back(make_pair(x, z)); // 使用 push_back 添加从y到x的边（因为树是无向的）
    // adj[x].emplace_back(y, z); 
    // adj[y].emplace_back(x, z); 
}

/*深度优先搜索，用于计算在给定最小长度lim下，可以形成的赛道数量。 
x 当前处理的节点编号, from 当前节点的父节点编号，以避免回溯。lim 当前候选的最小赛道长度。*/
void DFS(int x, int from, int lim){
    // 遍历所有与x相连的节点（子节点）
    for (const auto &edge : adj[x]){
        int child = edge.first;
        int weight = edge.second;
        if (child == from)
            continue; // 避免回到父节点
        // 递归调用DFS处理子节点
        DFS(child, x, lim);
    }
    // 初始化部分路径队列的尾指针
    tail = 0;
    // 收集所有子节点向上延伸的部分路径长度
    for (const auto &edge : adj[x]) {
        int child = edge.first;
        int weight = edge.second;
        if (child == from)
            continue;

        que[++tail] = dp[child] + weight; // 将子节点的最长路径加上边的长度
    }

    // 将部分路径按升序排序
    sort(que + 1, que + tail + 1);

    // 尝试直接选择那些已经大于等于lim的部分路径作为独立的赛道
    while (tail > 0 && que[tail] >= lim){
        tail--;        // 移除最大的部分路径
        res--;         // 需要形成的赛道数减少
    }

    // 尝试将剩余的较小路径与较大路径配对，形成赛道
    for (int i = 1; i <= tail; i++){
        if (tag[i] != x){ // 检查该路径是否未被选中
            int l = i + 1;
            int r = tail;
            int pst = tail + 1; // 初始化二分查找的目标位置
            // 二分查找，寻找最小的j使得que[i] + que[j] >= lim
            while (l <= r){
                int mid = (l + r) / 2;
                if (que[i] + que[mid] >= lim){
                    pst = mid;
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            // 如果找到的pst已经被选中，继续向后寻找
            while (pst <= tail && tag[pst] == x)
                pst++;

            // 如果找到合适的配对，标记这两条路径并减少剩余赛道数
            if (pst <= tail) {
                tag[i] = tag[pst] = x; // 标记这两条路径已被选中
                res--;                   // 需要形成的赛道数减少
            }
        }
    }

    // 更新当前节点x的dp值，选择未被选中的最长部分路径向上传递
    dp[x] = 0;
    for (int i = tail; i >= 1; i--){
        if (tag[i] != x){
            dp[x] = que[i];
            break; // 找到第一个未被选中的最长路径
        }
    }

    return;
}

int main(){
    //freopen("track.in","r",stdin);
    //freopen("track.out","w",stdout);

    // 输入节点数n和需要形成的赛道数m
    cin >> n >> m;
    // 输入n-1条边的信息，并构建邻接表
    for (int i = 1, x, y, z; i < n; i++){
        cin>>x>>y>>z;
        Addline(x, y, z); // 添加从x到y的边和从y到x的边
    }
  
    int root = 1;

    // 初始化二分查找的左右边界
    int l = 0, r = INF, ans = 0;
    while (l <= r){ // 二分查找答案
        int mid = (l + r) / 2; // 当前候选的最小赛道长度
        res = m;                // 重置剩余需要的赛道数
        memset(tag, 0, sizeof(tag)); // 重置标记数组
        DFS(root, 0, mid); // 执行DFS，计算可以形成的赛道数量
        if (res <= 0){
            // 如果可以形成足够的赛道，尝试更大的最小长度
            ans = mid;
            l = mid + 1;
        }
        else{
            // 如果无法形成足够的赛道，尝试更小的最小长度
            r = mid - 1;
        }
    }

    // 输出最终的答案
    cout << ans << endl;

    return 0;
}