526互联

Codeforces 894D Ralph And His Tour in Binary Country

发布时间 2023-05-01 19:59:56作者: lhzawa

预处理出对于 \(u\) 节点其子树内节点（包括 \(u\)）与 \(u\) 的距离，从小到大排序得到 \(ds_u\)
同时对 \(ds_u\) 进行前缀和处理 \(dh_{u, i} = \sum\limits_{j = 1}^{i} ds_{u, j}\)
这样设 \(tot\) 为 \(ds_u\) 二分得到的 \(ds_{u, i}\le h\) 的右端点，也即为 \(u\) 子树内对答案有贡献的点的数量。
拆一下贡献的式子：\(\sum\limits_{i = 1}^{tot} (h - ds_{u, i}) = tot\times h - \sum\limits_{i = 1}^{tot} (h - ds_{u, i}) = tot\times h - dh_{u, tot}\)
然后就可以 \(O(1)\) 求子树贡献了

对于询问：
首先可以得到 \(u\) 子树内对答案的贡献
发现还有子树外的贡献，便考虑类似容斥的思想：
\(u\) 一直往上跳（即 \(u\leftarrow fa_u\)）的同时计算 \(fa_u\) 这个子树的贡献，发现包含了 \(u\)，则减去 \(u\) 子树的贡献

注意因为每次往上跳都会跳 \(l_u\) 的长度，所以 \(fa_u\) 子树对应的 \(h_{fa}\) 要在往上跳时更新：\(h_{fa}\leftarrow h_{fa} - l_u\)
同时考虑 \(u\) 子树被 \(fa_u\) 子树包含，所以其对于 \(fa_u\) 子树还有贡献应该再多走 \(l_u\)，所以 \(u\) 子树对应 \(h_u\) 应为 \(h_{fa} - l_u\)

感觉写的好抽象（，看代码应该好些

#include<bits/stdc++.h>
using namespace std;
#define int64 long long
const int N = 1e6 + 10;
int64 l[N];
vector<int64> ds[N * 2], dh[N];
int lbcnt(int id, int64 sum) {
	return lower_bound(ds[id].begin() + 1, ds[id].end(), sum) - ds[id].begin() - 1;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 2; i <= n; i++) {
		scanf("%lld", &l[i]);
	}
	for (int i = n; i; i--) {
		for (int64 x : ds[i << 1]) {
			ds[i].push_back(x + l[i << 1]);
		}
		for (int64 x : ds[i << 1 | 1]) {
			ds[i].push_back(x + l[i << 1 | 1]);
		}
		inplace_merge(ds[i].begin(), ds[i].begin() + ds[i << 1].size(), ds[i].end());
		ds[i].insert(ds[i].begin(), 0);
	}
	for (int i = 1; i <= n; i++) {
		ds[i].insert(ds[i].begin(), 0);
		dh[i].push_back(0);
		for (int j = 1; j < (int)(ds[i].size()); j++) {
			dh[i].push_back(ds[i][j] + dh[i].back());
		}
	}
	for (int i = 1; i <= m; i++) {
		int u;
		int64 h;
		scanf("%d%lld", &u, &h);
		int tot = lbcnt(u, h);
		int64 ans = tot * h - dh[u][tot];
		int64 w = l[u];
		for (int v = u >> 1; v; u >>= 1, v >>= 1, w += l[u]) {
			int totu = lbcnt(u, h - w - l[u]), totv = lbcnt(v, h - w);
			ans += totv * (h - w) - dh[v][totv]; ans -= totu * (h - w - l[u]) - dh[u][totu];
		}
		printf("%lld\n", ans);
	}
	return 0;
}