| 148 | |
| 149 | // dfs2的迭代版 |
| 150 | public static void dfs4() { |
| 151 | stacksize = 0; |
| 152 | push(root, root, -1); |
| 153 | while (stacksize > 0) { |
| 154 | pop(); |
| 155 | if (edge == -1) { // edge == -1，表示第一次来到当前节点，并且先处理重儿子 |
| 156 | top[first] = second; |
| 157 | dfn[first] = ++cntd; |
| 158 | seg[cntd] = first; |
| 159 | if (son[first] == 0) { |
| 160 | continue; |
| 161 | } |
| 162 | push(first, second, -2); |
| 163 | push(son[first], second, -1); |
| 164 | continue; |
| 165 | } else if (edge == -2) { // edge == -2，表示处理完当前节点的重儿子，回到了当前节点 |
| 166 | edge = head[first]; |
| 167 | } else { // edge >= 0, 继续处理其他的边 |
| 168 | edge = next[edge]; |
| 169 | } |
| 170 | if (edge != 0) { |
| 171 | push(first, second, edge); |
| 172 | if (to[edge] != fa[first] && to[edge] != son[first]) { |
| 173 | push(to[edge], to[edge], -1); |
| 174 | } |
| 175 | } |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | public static void up(int i) { |
| 180 | sum[i] = (sum[i << 1] + sum[i << 1 | 1]) % MOD; |