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 代码实现如下：

CPP

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 记录

CPP

/*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协助完成树链剖分的代码。

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

文章操作