Menu
Article Graph

POJ 3728 The merchant

NodeKey

NodeKey

• 2 min read

LCA 好题！

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质：
深度优先搜索时的向下局部性。自己乱取得，蛤蛤蛤

题意：
给你一棵树，每个节点有一个权值。给你很多个询问，每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路：
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况：

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 – u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候，基于dfs，在你的眼里，当前节点就是向下整棵树的根节点，你完全不会去考虑往上的节点。
所以你现在使用的四个值，刚好是你当前节点的孩子节点的最优值。
基于这个事实，我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
Share