专栏文章

2025勰码公益营 B 班 37号 作业 1-2

pporse
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqbco9q
此快照首次捕获于
2025/12/04 02:01
3 个月前
此快照最后确认于
2025/12/04 02:01
3 个月前
查看原文

P1600 [NOIP 2016 提高组] 天天爱跑步 题解

题目大意

给定 nn 个节点的树，mm 个人分别走 mm 个路径，从时刻 00 开始走，1s1\text{s} 走一条边，询问对于每个点 ii，在时刻 wiw_i 有多少个人在点 ii 上。

思路

如果我们对于每个路径求点对他们的贡献，那么要么 TLE\text{TLE}（暴力），要么 MLE\text{MLE}（树剖+二维树状数组）。所以我们考虑拆贡献，对于点求路径对它的贡献。
对于一个点，wiw_i 上面有人有两种情况：
  1. 那个人还没到达 lcalca。
  2. 那个人已经到达 lcalca。

第一种情况

从 aa 经过 ii 走到 lcalca，什么时候在点 ii 呢？也就是走了 wiw_i 秒时，又因为此时深度一直减少，所以 aa 与 ii 的深度相差 wiw_i。
也就是说，当 deepi+wi=deepadeep_i + w_i = deep_a 时，路径对 ii 有 11 的贡献。

第二种情况

从 lcalca 经过 ii 走到 bb，什么时候在点 ii 呢？也就是走了 wi−dis(a,lca)w_i - \text{dis}(a, lca) 秒时，又因为此时深度一直增加，所以 ii 与 lcalca 的深度相差 wi−dis(a,lca)w_i - \text{dis}(a, lca)。
也就是说，当 deepi=deeplca+wi−dis(a,lca)deep_i = deep_{lca} + w_i - \text{dis}(a, lca)，即 deepi−wi=−deppa+2×depplcadeep_i - w_i = -depp_a + 2 \times depp_{lca} 时，路径对 ii 有 11 的贡献。
由于这个问题是离线的，我们考虑树上差分，对于每个路径，我们打四个标记：
  • 点 aa 打一个 (deepa,1)(deep_a, 1)。
  • 点 falcafa_{lca} 打一个 (deepa,−1)(deep_a, -1)。
  • 点 bb 打一个 (−deppa+2×depplca,1)(-depp_a + 2 \times depp_{lca}, 1)。
  • 点 falcafa_{lca} 打一个 (−deppa+2×depplca,−1)(-depp_a + 2 \times depp_{lca}, -1)。
我们开一个全局桶，跑 dfs，每个点的子树中对应标记变化量即为答案。

实现&细节

  • 打标记要每个点开一个 vector，要不然空间 O(n2)\mathcal{O}(n^2)，MLE\text{MLE}。
  • 由于桶中对一个点可能有贡献的只有两个下标，所以我们记变化量的时候每个点只需要开 O(1)\mathcal{O}(1) 个变量就行。
  • 如果一个路径对它的 lcalca 有贡献，那么我们会计算两次，这个要判掉。

Code

代码中我两种情况分开写了，其实可以一块写。
CPP
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 300010;

int n, m, a, b, w[maxn], ans[maxn];
map <int, int> t; // 这题开到 3e7 都 RE, 改成 map 就好了，不知道为啥
vector <int> G[maxn];
vector <pair <int, int> > tag1[maxn], tag2[maxn];

struct shupou { // 树剖求 LCA
	int r, depp[maxn], fa[maxn], hs[maxn], sz[maxn], lu[maxn], listt[maxn], ll[maxn], li;
	void init(int root) {
		r = root;
		depp[r] = 1;
		lu[r] = r;
		dfs1(r);
		dfs2(r);
		return ;
	}
	void dfs1(int u) {
		sz[u] = 1;
		int maxx = 0;
		for (int i = 0; i < G[u].size(); i++) {
			int now = G[u][i];
			if (now == fa[u]) continue;
			fa[now] = u;
			depp[now] = depp[u] + 1;
			dfs1(now);
			sz[u] += sz[now];
			if (sz[now] > maxx) hs[u] = now, maxx = sz[now];
		}
		return ;
	}
	void dfs2(int u) {
		listt[++li] = u;
		ll[u] = li;
		if (hs[u]) {
			lu[hs[u]] = lu[u];
			dfs2(hs[u]);
		}
		for (int i = 0; i < G[u].size(); i++) {
			int now = G[u][i];
			if (now == fa[u] || now == hs[u]) continue;
			lu[now] = now;
			dfs2(now);
		}
		return ;
	}
	int LCA(int x, int y) {
		if (lu[x] == lu[y]) {
			if (depp[x] > depp[y]) swap(x, y);
			return x;
		}
		if (depp[lu[x]] < depp[lu[y]]) swap(x, y);
		return LCA(fa[lu[x]], y);
	}
} sp;

void dfs1(int u) { // 统计从起点到 lca 的答案
	int lastt = t[sp.depp[u] + w[u]];
	for (pair <int, int> now : tag1[u]) {
		t[now.first] += now.second;
	}
	for (int now : G[u]) {
		if (now == sp.fa[u]) continue;
		dfs1(now);
	}
	ans[u] += t[sp.depp[u] + w[u]] - lastt;
	return ;
}
void dfs2(int u) { // 统计从 lca 到终点的答案
	int lastt = t[sp.depp[u] - w[u]];
	for (pair <int, int> now : tag2[u]) {
		t[now.first] += now.second;
	}
	for (int now : G[u]) {
		if (now == sp.fa[u]) continue;
		dfs2(now);
	}
	ans[u] += t[sp.depp[u] - w[u]] - lastt;
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	
	sp.init(1);
	for (int i = 1, lca; i <= m; i++) {
		cin >> a >> b;
		lca = sp.LCA(a, b);
		if (sp.depp[a] - sp.depp[lca] == w[lca]) ans[lca]--; // 特判：如果 lca 可以检测到，那么在下面的程序里会被通统计两次，所以在这里减掉一次
		tag1[sp.fa[lca]].push_back({sp.depp[a], -1});
		tag1[a].push_back({sp.depp[a], 1});
		tag2[sp.fa[lca]].push_back({-sp.depp[a] + 2 * sp.depp[lca], -1});
		tag2[b].push_back({-sp.depp[a] + 2 * sp.depp[lca], 1}); // 打标记
	}
	dfs1(1);
	dfs2(1); // 统计答案
	
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << ' ';
	}

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...