1. 题意理解

我们有一棵有根树（领导树），每个节点 $v_i$ 有一个级别 $w_i$，越高层的领导 $w_i$ 越小。

定义一个部门结点子集 $S$，满足：

对任意 $v_i, v_j \in S$，如果 $v_i$ 是 $v_j$ 的子孙，则 $w_i \ge w_j$。

换句话说：在祖先-后代关系中，祖先的级别必须小于等于后代的级别（因为 $w$ 越小表示越高层的领导，所以祖先的 $w$ 小，后代的 $w$ 大或相等）。

---

2. 条件转化

设 $v_a$ 是 $v_d$ 的祖先，那么条件要求： [ w_a \le w_d ] 即从根到叶子的路径上，$w$ 必须非递减。

所以我们要找树中一个最大的节点子集，使得任意根到该子集中某个叶子的路径上 $w$ 非递减。

---

3. 问题重述

在树中找一个最大的节点集合 $S$，使得：

• 如果 $u$ 是 $v$ 的祖先且 $u,v \in S$，那么 $w_u \le w_v$。

这等价于：在任意一条从根向下的路径上，如果选了多个节点，这些节点的 $w$ 必须非递减。

---

4. 思考解法

这是一个树上的最长非递减链类问题，但不同链可以共享节点吗？
注意：集合 $S$ 不要求连通，但必须满足祖先-后代的 $w$ 非递减条件。

所以我们可以这样想：

• 对每个节点 $u$，考虑以 $u$ 为最高层（$w$ 最小）的、包含 $u$ 的满足条件的最大集合大小。
• 但这样不好做，因为节点可能同时属于多个链。

---

5. 关键观察

设 $f(u)$ 表示在 $u$ 的子树中，选择 $u$ 且满足条件的最大节点数。

如果选择 $u$，那么 $u$ 的所有子孙如果要被选，必须满足 $w \ge w_u$。

所以我们可以递归地：

• 先把所有 $w < w_u$ 的子孙排除（如果选 $u$，这些子孙不能选，因为 $w$ 比 $u$ 小，违反非递减）。
• 然后对满足 $w \ge w_u$ 的子孙，可以独立地选择它们的最大满足条件的集合。

但这样直接做是 $O(n^2)$ 的，不可行。

---

6. 优化思路

考虑自底向上 DP，并利用数据结构合并子树信息。

定义 $dp[u]$ 表示在 $u$ 的子树中，所有被选节点的 $w$ 值 $\ge w_u$ 的最大节点数（不一定选 $u$ 自己，但这里我们考虑包含 $u$ 的情况）。

另一种更好定义的方式：

设 $g(u, \text{minW})$ 表示在 $u$ 的子树中，所选节点必须满足 $w \ge \text{minW}$ 的最大节点数。

那么： [ g(u, \text{minW}) = \max\left( g(u, \text{minW}), \sum_{v \in \text{children}(u)} g(v, \text{minW}) \right) ] 如果选 $u$，则要求 $w_u \ge \text{minW}$，并且新的 $\text{minW}$ 变成 $w_u$： [ g(u, \text{minW}) = \max\left( g(u, \text{minW}), 1 + \sum_{v \in \text{children}(u)} g(v, w_u) \right) ]

这样我们可以用线段树或平衡树（map）来维护每个节点 $g(u, \cdot)$ 函数，合并时用启发式合并（小的合并到大的）。

---

7. 具体算法

1. 自底向上处理树。
2. 每个节点 $u$ 维护一个 map<int, int>：f[w] 表示在 $u$ 子树中，所选节点最小 $w$ 值至少为 $w$ 时的最大节点数。
3. 初始时，f[w_u] = 1。
4. 对每个子节点 $v$：
   • 如果 $u$ 的 f 比 $v$ 的 f 小，则交换（启发式合并）。
   • 把 $v$ 的 f 合并到 $u$ 的 f 中：
     对每个 $(\text{minW}, \text{val})$ 在 $v$ 的 f 中，更新
     u_f[ minW ] = max(u_f[minW], val)。
5. 然后考虑选 $u$ 自己：
   找到 $u$ 的 f 中所有 $w \ge w_u$ 的项，取最大值 $M$，
   然后 u_f[ w_u ] = max(u_f[w_u], M+1)。
6. 最后，根节点的 f 中的最大值就是答案。

---

8. 复杂度分析

启发式合并的复杂度是 $O(n \log^2 n)$，因为每次合并是 $O(\text{小的大小} \cdot \log n)$，并且每个节点最多被合并 $\log n$ 次。

---

9. 样例验证

样例：

6
2 5 1 3 5 4
1
1
2
2
4

树结构：

1(w=2)
├── 2(w=5)
│   ├── 4(w=3)
│   └── 5(w=5)
└── 3(w=1)
    └── 6(w=4)

我们手动找最大集合：
可以选 {1, 2, 5, 6}（1→2: 2≤5, 1→6: 2≤4, 2→5: 5≤5），大小 4。
输出 4，符合。

---

10. 总结

本题是树形 DP 结合启发式合并的经典题，关键在于定义状态为 g(u, minW) 表示在 $u$ 子树中，所选节点 $w$ 值至少为 minW 的最大节点数，并用 map 维护，通过启发式合并得到 $O(n \log^2 n)$ 的解法。