| 257 | |
| 258 | // 从x到y的路径上，查询所有节点的累加和 |
| 259 | public static long pathSum(int x, int y) { |
| 260 | long ans = 0; |
| 261 | while (top[x] != top[y]) { |
| 262 | if (dep[top[x]] <= dep[top[y]]) { |
| 263 | ans = (ans + query(dfn[top[y]], dfn[y], 1, n, 1)) % MOD; |
| 264 | y = fa[top[y]]; |
| 265 | } else { |
| 266 | ans = (ans + query(dfn[top[x]], dfn[x], 1, n, 1)) % MOD; |
| 267 | x = fa[top[x]]; |
| 268 | } |
| 269 | } |
| 270 | ans = (ans + query(Math.min(dfn[x], dfn[y]), Math.max(dfn[x], dfn[y]), 1, n, 1)) % MOD; |
| 271 | return ans; |
| 272 | } |
| 273 | |
| 274 | // x的子树上，查询所有节点的累加和 |
| 275 | public static long subtreeSum(int x) { |