自动搬运

查看原文

来自洛谷，原作者为

	JoyLosingK **

搬运于2025-08-24 23:14:56，当前版本为作者最后更新于2025-04-28 21:43:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

维护一棵带点权的树，初始时每个点的权值 $w_i$ 为 $0$，支持以下操作：

• 子树加 $x$。
• 询问一条以 $1$ 号点开始的路径，使得路径上的 $a_i\le w_i$ 的点的数量最多。

题解

刚开始看到这道题时觉得很不可做。首先想到的是分块，对每个块维护排序后的块，区间加散块暴力重构。询问时，散块暴力，整块二分答案求解。时间复杂度为 $O((n+q)\sqrt n\log n)$，貌似只有 $51$ 分。

看到 $5\times 10^5$ 的 $n$，猜测是一只 $\log$。观察题目后发现一个细节之处，就是子树加上的数是正数！这意味着当某个点 $i$ 满足 $a_i\le w_i$ 后，它将永远符合条件。

于是我们考虑势能线段树，对于线段树每个节点维护最大值，先使每个点 $i$ 的 $w_i=-a_i$。在每次子树加操作结束后递归去找新的符合条件的点。

递归过程中，若当前区间的最大值小于 $0$，那么这个区间中一定没有符合条件的点，直接返回。

最后就是统计答案，发现每个符合条件的点对答案的贡献的部分显然是以它为根的子树，直接用线段树维护即可。 最终的答案显然就是整个答案序列中的最大值。

时间复杂度

由于每个点只会被更新（由不符合条件变为符合条件）一次，$n$ 个点就是 $O(n\log n)$ 的复杂度。其他普通的线段树操作也是 $O(n\log n)$ 的，所以总时间复杂度为 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define rint register int
#define lb(i) (i&(-i))
const int N = 5e5 + 5;
int n, q, a[N], dfn[N], sz[N], rdfn[N], now;
vector<int> e[N];
char buf[83886000], *p1 = buf, *p2 = buf, ubuf[83886000], *u = ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,83886,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	return x * f;
}
struct tree1 {
	int l, r, mx, tg;
#define l1(z) t1[z].l
#define r1(z) t1[z].r
#define mx1(z) t1[z].mx
#define tg1(z) t1[z].tg
} t1[N << 2];
struct tree2 {
	int l, r, mx, tg;
#define l2(z) t2[z].l
#define r2(z) t2[z].r
#define mx2(z) t2[z].mx
#define tg2(z) t2[z].tg
} t2[N << 2];
inline void build1(int k, int l, int r) {
	l1(k) = l, r1(k) = r;
	if (l == r) return;
	int mid = l + r >> 1;
	build1(k << 1, l, mid), build1(k << 1 | 1, mid + 1, r);
}
inline void pushdown1(int k) {
	if (tg1(k)) {
		mx1(k << 1) += tg1(k), mx1(k << 1 | 1) += tg1(k),
	    tg1(k << 1) += tg1(k), tg1(k << 1 | 1) += tg1(k);
	}
	return (void)(tg1(k) = 0);
}
inline void Add1(int k, int x, int y, int v) {
	if (x <= l1(k) && r1(k) <= y) {
		mx1(k) += v, tg1(k) += v;
		return;
	}
	if (r1(k) < x || y < l1(k)) return;
	pushdown1(k), Add1(k << 1, x, y, v), Add1(k << 1 | 1, x, y, v);
	mx1(k) = max(mx1(k << 1), mx1(k << 1 | 1));
}
inline int Ans() {
	return mx1(1);
}
inline void build2(int k, int l, int r) {
	l2(k) = l, r2(k) = r;
	if (l == r) {
		mx2(k) = -a[rdfn[l]];
		return;
	}
	int mid = l + r >> 1;
	build2(k << 1, l, mid), build2(k << 1 | 1, mid + 1, r);
	mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void pushdown2(int k) {
	if (tg2(k)) {
		mx2(k << 1) += tg2(k), mx2(k << 1 | 1) += tg2(k),
	    tg2(k << 1) += tg2(k), tg2(k << 1 | 1) += tg2(k);
	}
	return (void)(tg2(k) = 0);
}
inline void Add2(int k, int x, int y, int v) {
	if (x <= l2(k) && r2(k) <= y) {
		mx2(k) += v, tg2(k) += v;
		return;
	}
	if (r2(k) < x || y < l2(k)) return;
	pushdown2(k), Add2(k << 1, x, y, v), Add2(k << 1 | 1, x, y, v);
	mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void find(int k) {
	if (mx2(k) < 0) return;
	if (l2(k) == r2(k)) {
		Add1(1, l2(k), l2(k) + sz[rdfn[l2(k)]] - 1, 1);
		return void(mx2(k) = -1e9);
	}
	pushdown2(k), find(k << 1), find(k << 1 | 1),
	mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void dfs(int u) {
	dfn[u] = ++now, rdfn[now] = u, sz[u] = 1;
	for (int v : e[u]) dfs(v), sz[u] += sz[v];
}
int main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	n = read(), q = read();
	for (int i = 2, x; i <= n; i++) x = read(), e[x].push_back(i);
	for (int i = 1; i <= n; i++) a[i] = read();
	dfs(1);
	build1(1, 1, n), build2(1, 1, n);
	for (int u, x; q--;) {
		u = read(), x = read();
		Add2(1, dfn[u], dfn[u] + sz[u] - 1, x), find(1);
		cout << Ans() << endl;
	}
	return 0;
}

感谢管理员的审核，也感谢读者们的阅读。求赞 qaq。