CF1413F Roads and Ramen

发表于 分类于 ， ， 阅读次数：

题意：给定一棵 个点的树，边权为 。

现在有 次修改边权的操作，每次操作后求当前树上最长的有偶数个 的简单路径包含多少条边。

，时限 。

路径有偶数个 等价于 和为 。

利用异或的自反性，设 为根到 路径的异或和，则路径 合法当且仅当 。修改边权相当于将子树内的 取反。

考虑欧拉序维护。

  • 结论： 一定在欧拉序 中出现，且是深度最小的那个点。

观察 放到欧拉序上，则有 考虑在线段树上维护这样的 状物。（ 可以和 重合）设：

  • 为区间 最小值。

  • 为满足 的 的最大值。

  • 为满足 的 的最大值，要求 在 右侧。即 的部分。

  • 为满足 的 的最大值，要求 在 左侧。即 的部分。

  • 维护 为候选答案，即 的 的最大值，要求 。

转移如下：

1
2
3
4
5
6
7
8
9
10
11
void up(int u) {
	Node &U = a[u], &L = a[u*2], &R = a[u*2+1];
	U.x0 = min(L.x0, R.x0);
	U.s = max(L.s, R.s);
	for (int e=0; e<=1; e++) {
		U.x1[e] = max(L.x1[e], R.x1[e]);
		U.ls[e] = max(max(L.ls[e], R.ls[e]), L.x1[e]-2*R.x0);
		U.rs[e] = max(max(L.rs[e], R.rs[e]), R.x1[e]-2*L.x0);
		U.s = max(U.s, max(L.ls[e]+R.x1[e], L.x1[e]+R.rs[e]));
	}
}

子树内 取反可以用懒标记处理（只需交换 ，余者同理）

复杂度 。