倍增 #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 50; int n, m, s; int head[N], tot; int lg[N]; // log2(i)+1 int fa[N][22], dep[N]; struct Edge { int …

点差分 例题：P3128 [USACO15DEC]Max Flow P 题目大意： 给 $k$ 条树上路径，求哪个点被经过的次数最多、被经过了多少次。 解题思路： 树上差分算法。对于每条路径 $(a,b)$，对 num[a]++，num[b]++，num[lca(a, b)]--，num[fa[lca(a, b)]]--。 这样再做一次 dfs 后…