题意重述

我们有一棵 $n$ 个节点的树，每个节点权值 $v_i \in \{-1, 1\}$。
要找一条简单路径，设路径上节点权值依次为 $a_1, a_2, \dots, a_k$，满足：

1. 任意前缀和 $\ge 0$。
2. 总和 $= 0$。
3. 定义 NP 值 = 前缀和的最大值。

求最大可能的 NP 值，若不存在这样的路径输出 $0$。

---

第一步：转化为括号序列问题

令 $1$ 对应左括号 (（权值 $+1$），$-1$ 对应右括号 )（权值 $-1$）。

条件 1 和 2 等价于：序列是合法括号序列。
条件 3：NP 值 = 前缀和的最大值，即括号序列的最大嵌套深度。

例如：

• 序列 (()()) 权值：$1,1,-1,1,-1,-1$，前缀和：$1,2,1,2,1,0$，NP = 2。
• 序列 ()() 权值：$1,-1,1,-1$，前缀和：$1,0,1,0$，NP = 1。

问题变为：
在树上找一条简单路径，使得路径上的权值序列是合法括号序列，且最大嵌套深度最大。

---

第二步：思考路径性质

假设路径 $u \to v$ 合法，设路径长度为 $L$（节点数）。
因为总和 $=0$，所以 $L$ 为偶数，且其中有 $L/2$ 个 $1$ 和 $L/2$ 个 $-1$。
最大嵌套深度 $= \max(\text{前缀和})$，取值范围 $[1, L/2]$。

我们要最大化这个值。

---

第三步：点分治框架

树上路径统计问题常用点分治。
考虑经过分治中心 $c$ 的路径 $u \to c \to v$（$u,v$ 在不同子树中）。

对路径 $c \to x$（$x$ 在子树中），记录以下信息：

• $sum$：$c$ 到 $x$ 的权值和（从 $c$ 出发）。
• $minpre$：$c$ 到 $x$ 路径上前缀和的最小值（从 $c$ 出发）。
• $maxpre$：$c$ 到 $x$ 路径上前缀和的最大值（从 $c$ 出发）。

注意：这里的前缀和是从 $c$ 开始计算的，即第一个权值是 $c$ 的权值（如果 $c$ 在路径中间，我们分两段处理）。

---

第四步：路径合并条件

对于 $c \to u$ 和 $c \to v$ 两段（$u,v$ 在不同子树），拼接成 $u \to c \to v$ 路径时：

设 $c \to u$ 的 $sum = S_u$，$minpre = m_u$，$maxpre = M_u$。
$c \to v$ 的 $sum = S_v$，$minpre = m_v$，$maxpre = M_v$。

拼接后路径的权值序列为 $u \to c$ 反转再接 $c \to v$。
但直接反转 $u \to c$ 不方便，我们换种方式：

考虑路径 $u \to c \to v$ 的权值序列，从 $u$ 开始：

1. 先走 $u \to c$，设这段的权值序列为 $A$（长度 $len_A$）。
2. 再走 $c \to v$，序列为 $B$（长度 $len_B$）。

$A$ 的总权值和 $= S_{uc}$（从 $u$ 到 $c$ 的和）。
$B$ 的总权值和 $= S_{cv}$（从 $c$ 到 $v$ 的和，这里 $S_{cv} = sum_v$）。

由于整条路径总和 $=0$，所以 $S_{uc} + S_{cv} = 0$。

---

更简单的处理方式

换一种拼接方法：
将 $u \to c$ 的路径反转，变成从 $c$ 到 $u$ 的路径，此时权值和取反，且前缀和最值会变化。

设 $c \to u$ 的 $sum = S$，$minpre = m$，$maxpre = M$。
那么从 $u$ 到 $c$ 的权值和 $= -S$，并且从 $u$ 到 $c$ 的前缀和最值不容易直接由 $m,M$ 得到，但可以通过原始序列反转推导。

不过这样复杂，我们采用更常用技巧：
在点分治时，对中心 $c$，我们分别处理 $c$ 的每个子树，计算 $c$ 到子树中节点 $x$ 的信息 $(sum, minpre, maxpre)$。

对于拼接 $u \to c \to v$，路径权值序列 = $(u \to c) \oplus (c \to v)$。
我们枚举 $u$ 和 $v$，要求：

1. $S_u + S_v = 0$（总权值和 $=0$）。
2. $minpre_u \ge 0$（$u \to c$ 段自身合法）。
3. $S_u + minpre_v \ge 0$（$u \to c$ 后再走 $c \to v$ 的前缀最小非负）。

---

第五步：计算 NP 值

对于满足条件的 $u,v$，整条路径的前缀和最大值出现在：

• 可能在 $u \to c$ 段：$maxpre_u$。
• 可能在 $c \to v$ 段：$S_u + maxpre_v$（因为 $u \to c$ 贡献了 $S_u$，再加 $c \to v$ 的前缀和）。

所以 NP = $\max(maxpre_u, S_u + maxpre_v)$。

我们要最大化这个值。

---

第六步：点分治实现细节

1. 找重心：标准点分治。
2. 处理子树：对每个子树 DFS，计算从中心 $c$ 到节点 $x$ 的 $(sum, minpre, maxpre)$。
   • 初始 $sum = v_c$（如果 $c$ 是起点，其实我们算 $c \to x$ 时起点是 $c$，$sum$ 是 $c$ 到 $x$ 的权值和）。
   • $minpre$ 是路径 $c \to x$ 上以 $c$ 为起点的前缀和最小值。
   • $maxpre$ 是前缀和最大值。
3. 合并信息：
   维护一个数组或哈希表 $mp[s]$，记录 $sum = s$ 的所有路径中，对应的 $(minpre, maxpre)$ 信息。
   因为我们要匹配 $sum$ 互为相反数的路径，且满足 $minpre \ge 0$ 和 $S_u + minpre_v \ge 0$。
   对于当前子树的每个路径 $(s, m, M)$，查询 $mp[-s]$ 中满足 $m' \ge 0$ 且 $s + m' \ge 0$ 的条目，计算 NP 值更新答案。
4. 更新信息：将当前子树的路径信息加入 $mp$，用于与后面子树合并。

---

第七步：特例：单段路径

除了拼接两段，也要考虑单段路径（$c$ 到某点 $x$ 自身就是合法括号序列且总和 $=0$）。
此时 $sum=0$ 且 $minpre \ge 0$，NP = $maxpre$。

---

第八步：复杂度

点分治 $O(n \log n)$，每层 DFS 子树 $O(size)$，合并时利用 $sum$ 范围 $[-n,n]$ 用数组存，$O(n)$ 处理每层。
总复杂度 $O(n \log n)$。

---

第九步：样例验证

样例：

5
0 -1
1 1
1 -1
2 1
2 -1

权值：$v_1=-1, v_2=1, v_3=-1, v_4=1, v_5=-1$。

树结构： 1 是根，孩子 2,3。
2 的孩子 4,5。

合法括号序列路径：例如 $4(1) \to 2(1) \to 3(-1)$ 权值：$1,1,-1$ 不合法（总和不为 0）。
要找总和为 0 且前缀和非负的路径。

试 $4(1) \to 2(1) \to 1(-1)$：$1,1,-1$ 总和 1，不符合。
实际上可以找到一条路径 $4 \to 2 \to 5$：权值 $1,1,-1$ 不合法。
最终答案 $2$ 可能来自路径 $4(1) \to 2(1) \to 1(-1) \to 3(-1)$？但简单路径不能重复点。

通过点分治可找出最大 NP=2 的路径。

---

第十步：总结

本题核心步骤：

1. 将问题转化为树上找合法括号序列路径，最大化最大嵌套深度。
2. 使用点分治处理经过某点的路径。
3. 维护 $sum, minpre, maxpre$ 信息，合并时检查合法性条件并更新 NP 值。
4. 注意单段路径也要考虑。

---