专栏文章

回忆

RRegister_int-std=c++14
P13663题解参与者 10已保存评论 11

文章操作

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

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

O(n2)O(n^2)

你发现 fuf_u 其实就是 uu 到子树内节点的最大距离。暴力维护即可。期望得分 3535。

O(nlog⁡2n)O(n \log^2 n)

离线把树建出来。可以发现每加一个点相当于给一条链 +1+1。所以说每次你要干这个事情：
  • 向上找到要 +1+1 的链的端点。
  • 把答案加上这条链上 aia_i 的和。
  • 给链 +1+1。
可以树剖套线段树二分简单做掉。直接维护 depu+fudep_u+f_u 可能会好写一点。期望得分 6060。

O(nlog⁡n)O(n\log n)

毛毛虫坐火箭包。给 LCT、全局平衡二叉树、以及被卡常的正解。期望得分 7070。

O(n)O(n)

树剖菜了，究其本质就是重链剖分跟这个 fif_i 的相性不太好。那这个 fif_i 的形式让你想到了什么？
考虑长剖，从叶子往根做，转而维护每个点加入时答案的变化量。对于每个点 uu，我们维护 uu 所在长链下方的所有节点的贡献。uu 本身维护加法标记 tut_u，下方的节点维护这个节点的实际 ff 值与 tut_u 的偏差值。
现在我们要处理 uu 与短儿子 vv 所有标记的合并。从上往下暴力枚举，对于同一深度的儿子，如果 uu 一侧比 vv 一侧的编号小，那么说明 uu 这一侧比 vv 这一侧先加入，上方的节点都已经被 uu 修改掉，那么 vv 已经没用，可以直接结算。否则，uu 这边在 vv 一侧之后、且深度小于等于他的标记全部都没用了，要将其全部结算，删除这些标记，再把 vv 的标记插过来。
对于长儿子的继承，直接继承其加法标记，加上自己的 aua_u，再将自己实际 fuf_u 与的 tut_u 偏差值设为 −tu-t_u 即可。
关于复杂度分析，标记的插入删除可以链表维护，由于长链维护的有效标记的数量不会大于长链长度，可以沿用长剖的复杂度分析，总复杂度 O(n)O(n)。
CPP
#include <bits/stdc++.h>

using namespace std;

// fastIO by d0j1a_1701

typedef long long ll;

const int MAXN = 5e6 + 10;
const int mod = 1e9 + 7;

inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); }

vector<int> g[MAXN]; int d[MAXN], md[MAXN], son[MAXN];

void init(int u) {
	for (int v : g[u]) {
		md[v] = d[v] = d[u] + 1, init(v);
		md[u] = max(md[u], md[v]);
		if (md[son[u]] < md[v]) son[u] = v;
	}
}

int n, a[MAXN], ans[MAXN], tag[MAXN];

struct node {
	int x, nxt;
	node() : x(0), nxt(0) {}
} l[MAXN];

void dfs(int u) {
	if (!son[u]) return ;
	dfs(son[u]), tag[u] = tag[son[u]], l[u].nxt = son[u];
	for (int v : g[u]) {
		if (v == son[u]) continue; dfs(v); int lst = u;
		for (int i = l[u].nxt, j = v; j; i = l[i].nxt, j = l[j].nxt) {
			if (i < j) ans[j] = add(l[j].x, tag[v]), lst = i;
			else {
				ans[i] = add(l[i].x, tag[u]);
				l[lst].nxt = j, swap(l[i].nxt, l[j].nxt);
				swap(i, j), lst = i;
				cadd(l[i].x, sub(tag[v], tag[u]));
			}
		}
	}
	cadd(tag[u], a[u]); if (tag[u]) l[u].x = mod - tag[u];
}

int main() {
	io.read(n, a[1]), n++;
	for (int i = 2, u; i <= n; i++) io.read(u, a[i]), g[u].emplace_back(i);
	init(1), dfs(1);
	for (int i = l[1].nxt; i; i = l[i].nxt) ans[i] = add(l[i].x, tag[1]);
	for (int i = 2; i <= n; i++) cadd(ans[i], ans[i - 1]), io.writeln(ans[i]);
}
这个放 T2 对洛谷来说可能还是有点超前了。

评论

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

正在加载评论...