Lucien

UPC-5909 - 货物运输 - 倍增LCA

20
2018/03

# UPC-5909 - 货物运输 - 倍增LCA

## 题目链接：

http://exam.upc.edu.cn/problem.php?id=5909

## 题目：

### 样例输入

6 5
1 2 2
2 3 5
2 4 2
2 5 3
5 6 1
2 4
6 2
1 3
3 5
1 6

### 样例输出

2
1
2
3
1

## 思路：

倍增求一下lca，然后再倍增求一下路径上的最小值即可，复杂度$O(m \times log_2n)$，觉得可以求lca的同时求出路径最小值，但是不知道为什么这样写会WA。

## 实现：

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7, maxm = int(4e5) + 7, inf = 0x3f3f3f3f;
int n, m;
struct Lca {
int dep[maxn], up[maxn][32], min[maxn][32], cnt, head[maxn];
struct { int next, to, val; } edge[maxm];
void addedge(int u, int v, int w) {
}
Lca() {
cnt = 0;
memset(up, 0xff, sizeof(up));
memset(min, 0x3f, sizeof(min));
}
void init(int n) {
std::queue<int> que;
que.emplace(dep[1] = 1); // 下标从1开始
int u, v;
while (!que.empty()) {
u = que.front(), que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
v = edge[i].to;
if (dep[v]) continue ;
up[v][0] = u, min[v][0] = edge[i].val, dep[v] = dep[u] + 1, que.push(v);
}
}
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
if (~up[i][j - 1]) {
up[i][j] = up[up[i][j - 1]][j - 1];
min[i][j] = std::min(min[i][j - 1], min[up[i][j - 1]][j - 1]);
}
}
int query(int u, int v) {
int ret = inf;
if (dep[u] < dep[v]) std::swap(u, v);
int tmp = dep[u] - dep[v];
for (int j = 0; tmp; j++)
if (tmp & (1 << j)) tmp ^= (1 << j), u = up[u][j];
if (u == v) return v;
for (int j = 20; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j], v = up[v][j];
}
}
return up[u][0];
}
int calc(int u, int lca) {
int ret = inf, tmp = dep[u] - dep[lca];
for (int i = 0; tmp; i++) {
if (tmp & (1 << i)) {
tmp ^= (1 << i);
ret = std::min(min[u][i], ret);
u = up[u][i];
}
}
return ret;
}
} lca;

int solve(int u, int v) {
int pre = lca.query(u, v);
return std::min(lca.calc(u, pre), lca.calc(v, pre));
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
}