题解：P11324 【MX-S7-T2】「SMOI-R2」Speaker

· · 题解

BFS + 树链剖分

题目描述

原题链接

前言

什么 DP，什么换根，不会写，怎么办？

其实这道题根本不需要！

只需要简单的 BFS 也可轻松解决！

解题思路

我们将 bfs_{i} 的初始值设为 c_{i}，依次将每个点 i 压入队列开始 BFS，如果从 i 点出发到 j 点并回来的总收入更优，即 bfs_{i} < bfs_{j} - 2 \times dis _ {ij}，则更新 bfs_{i}，并将 j 压入队列。

最后我们得到的 bfs_{i} 表示从 i 点出发，开完第二场演讲并回来到点 i 可获得利润的最大值。

BFS 代码实现如下：

for (int i = 1; i <= n; ++i)
    bfs[i] = c[i];
for (int i = 1; i <= n; ++i) 
{
    queue<int> q;
    q.push(i);
    while (!q.empty())
    {
        int w = q.front(); q.pop();
        for (Edge j : mp[w])
        if (bfs[j.to] < bfs[w] - j.ct * 2)
        {
            bfs[j.to] = bfs[w] - j.ct * 2;
            q.push(j.to);
        }
    }
}

然后我们使用树链剖分 + ST 表，维护区间 bfs_{i} 的最大值即可。

代码实现

AC 记录

/*BFS + Heavy-Light Decomposition*/
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN = 2e5 + 10;

struct Edge {
    int to, ct;
    bool operator< (const Edge &rhs) const {
        return rhs.ct < ct;
    }
};
vector<Edge> mp[MAXN];

int c[MAXN];
int bfs[MAXN], ans[MAXN], dis[MAXN], pre[MAXN];
int f[MAXN], sz[MAXN],son[MAXN], top[MAXN], id[MAXN];
int st[MAXN][20 + 5];
int cnt;

void dfs1(int x, int fa)
{
    dis[x] = dis[fa] + 1;
    f[x] = fa;
    int maxson = -1;
    for (Edge i : mp[x])
        if (i.to != fa)
        {
            pre[i.to] = pre[x] + i.ct;
            dfs1(i.to, x);
            sz[x] += sz[i.to];
            if (sz[i.to] > maxson)
            {
                maxson = sz[i.to];
                son[x] = i.to;
            }
        }
    sz[x]++;
}

void dfs2(int x, int ntop)
{
    id[x] = ++cnt;
    top[x] = ntop;
    if (!son[x]) return;
    dfs2(son[x], ntop);
    for (Edge i : mp[x])
    {
        if (i.to == f[x] || i.to == son[x]) continue;
        dfs2(i.to, i.to);
    }
}

int ask(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

signed main()
{
    //freopen("speaker.in", "r", stdin);
    //freopen("speaker.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= n - 1; ++i)
    {
        int u, v, ct;
        cin >> u >> v >> ct;
        mp[u].push_back({v, ct});
        mp[v].push_back({u, ct});
    }
    for (int i = 1; i <= n; ++i)
        bfs[i] = c[i];
    for (int i = 1; i <= n; ++i)//BFS 
    {
        queue<int> q;
        q.push(i);
        while (!q.empty())
        {
            int w = q.front(); q.pop();
            for (Edge j : mp[w])
                if (bfs[j.to] < bfs[w] - j.ct * 2)
                {
                    bfs[j.to] = bfs[w] - j.ct * 2;
                    q.push(j.to);
                }
        }
    }
    dfs1(1, 1);
    dfs2(1, 1);
    for (int i = 1; i <= n; ++i)
        ans[id[i]] = bfs[i];
    for (int i = 1; i <= n; ++i)//ST
        st[i][0] = ans[i];
    int maxk = log(n) / log(2) + 1;
    for (int j = 1; j <= maxk; ++j)
        for (int i = 1; i + (1 << j) <= n + 1; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i <= q; ++i)
    {
        int x, y;
        cin >> x >> y;
        int val = LLONG_MIN;
        int fx = x, fy = y;
        while (top[x] != top[y])
        {
            if (dis[top[x]] < dis[top[y]]) swap(x, y);
            val = max(val, ask(id[top[x]], id[x]));
            x = f[top[x]];
        }
        if (dis[x] > dis[y]) swap(x, y);
        val = max(val, ask(id[x], id[y]));
        val = max(val, ans[id[x]]);
        int dxy = pre[fx] + pre[fy] - 2 * pre[x];
        cout << c[fx] + val + c[fy] - dxy << endl;
    }
    return 0;
}

特别鸣谢

感谢 @consequence协助完成树链剖分的代码。