SP3978 DISQUERY – Distance Query

发布于 2019-10-23  313 次阅读


Link

题意不说了,翻译已经是简明题意了。

很容易想到要求一个LCA,这里可以用到两种方法来解决。

可以使用树剖求LCA,但是考虑到树剖是可以处理点权的,在这里我们要转化成边权。所以不是很好处理。

那就是倍增了,稍微想一下就可想到在倍增的同时记两个数组Min[][] Max[][], 在倍增的同时处理出到当前节点的最小边和最大边。

思路大概是这样,具体实现也很板子,见代码

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;

int n, Q, num, t;
int head[SIZE], depth[SIZE], dis[SIZE], f[SIZE][21], Min[SIZE][21], Max[SIZE][21];

struct node {
    int to, v, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].to = y;
    edge[num].v = z;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int u, int fa)
{
    f[u][0] = fa;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != fa) {
            Min[v][0] = Max[v][0] = edge[i].v; // 赋初值
            depth[v] = depth[u] + 1;
            DFS(v, u);
        }
    }
}

inline void init()
{
    for (int k = 1; k <= 20; k++)
        for (int i = 1; i <= n; i++) {
            if (f[f[i][k - 1]][k - 1] && f[i][k - 1]) {
                f[i][k] = f[f[i][k - 1]][k - 1];
                Min[i][k] = std::min(Min[i][k - 1], Min[f[i][k - 1]][k - 1]);
                Max[i][k] = std::max(Max[i][k - 1], Max[f[i][k - 1]][k - 1]); // 预处理倍增数组的时候同时处理Min Max两个数组
            }
        }
}

inline void LCA(int u, int v)
{
    int ans_min = 2e9, ans_max = -2e9;
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int i = 20; i >= 0; i--) {
        if (depth[u] <= depth[f[v][i]]) {
            ans_min = std::min(ans_min, Min[v][i]), ans_max = std::max(ans_max, Max[v][i]); // 跳的时候记最大最小值,一定要注意先记再跳
            v = f[v][i];
        }
    }
    if (u == v) {
        printf("%d %d\n", ans_min, ans_max);
        return;
    }
    for (int i = 20; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            ans_min = std::min(ans_min, std::min(Min[u][i], Min[v][i])), ans_max = std::max(ans_max, std::max(Max[u][i], Max[v][i]));
            u = f[u][i], v = f[v][i];
        }
    }
    ans_min = std::min(ans_min, std::min(Min[u][0], Min[v][0]));
    ans_max = std::max(ans_max, std::max(Max[u][0], Max[v][0])); // 跟第0层比较
    printf("%d %d\n", ans_min, ans_max);
}

int main()
{
    int u, v, d;
    n = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read(), d = read();
        Addedge(u, v, d);
        Addedge(v, u, d);
    }
    depth[1] = 1;
    DFS(1, 0);
    Min[1][0] = 2e9;
    init();
     Q = read();
     while (Q--) {
         u = read(), v = read();
         LCA(u, v);
     }
    return 0;
}

朴实沉毅