题解 | #城市网络#

考察知识点：树上 DFS、倍增

本题很容易想到模拟的方式，但时间复杂度为 ，会超时。

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 1e5 + 5;
vector<int> edges[N];
int fa[N], a[N];

void dfs(int u, int from)
{
    fa[u] = from;
    for (int v : edges[u])
        if (v != from)
            dfs(v, u);
}

void query(int u, int v, int c)
{
    int ans = 0, m = c;
    while (u != fa[v])
    {
        if (a[u] > m)
            ans++;
        m = max(m, a[u]);
        u = fa[u];
    }
    cout << ans << endl;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1, 0);
    while (q--)
    {
        int u, v, c;
        cin >> u >> v >> c;
        query(u, v, c);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

使用 倍增 来优化程序，我们不用每次只向上跳一步，而是每次向上跳 步。

详解如下代码，其中 fa[i][j] 为从 i 点开始，购买了 次珠宝的节点，dep[i] 为节点 i 到根节点的距离（即深度），to[i] 为第 次询问的终点，a[n + i] 为第 次询问的初始珠宝价值。

时间复杂度：

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 2e5 + 5, LOGN = 20;
vector<int> edges[N];
int a[N], fa[N][LOGN];
int dep[N], to[N];

void dfs(int u, int from)
{
    dep[u] = dep[from] + 1;
    int f0 = from;
    // fa[u][0] 为从 u 节点出发，购买了 2^0 = 1 次珠宝的节点
    if (a[from] > a[u]) // 如果父节点刚好是满足条件的节点
        fa[u][0] = from;
    else // 否则向上跳
    {
        for (int i = LOGN - 1; i >= 0; i--)            // 从大到小枚举
            if (fa[from][i] && a[fa[from][i]] <= a[u]) // 从父节点开始向上跳
                from = fa[from][i];
        fa[u][0] = fa[from][0]; // 事实上，fa[u][0] 就是 u 往上走的第一个 a 值比 u 大的节点
    }
    for (int i = 1; i < LOGN; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 2^i = 2^(i-1) + 2^(i-1)
    for (int v : edges[u])                  // 遍历所有子节点
        if (v != f0)
            dfs(v, u);
}

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    for (int i = 1; i <= q; i++) // 为了考虑 u 点
    {
        int u, v, c;
        cin >> u >> v >> c;
        edges[i + n].push_back(u);
        edges[u].push_back(i + n);
        to[i] = v, a[i + n] = c;
    }
    dfs(1, 0);
    for (int i = 1; i <= q; i++)
    {
        int u = n + i, v = to[i], ans = 0;
        for (int i = LOGN - 1; i >= 0; i--)
            if (dep[fa[u][i]] >= dep[v]) // 尝试向上跳 2^i 步
            {
                u = fa[u][i];
                ans += 1 << i;
            }
        cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}