CF1797F Li Hua and Path
给定一个 \(n\) 个点的树。求下列两个条件中恰好满足一个的路径 \(x\to y(x<y)\) 的数量：
- \(x\) 的编号是路径上的最小值。
- \(y\) 的编号是路径上的最大值。
同时有 \(q\) 次操作，第 \(i\) 操作新增编号为 \(n+i\) 的点和将其连到树上的边。输出每次操作后的答案。
\[n\le 5\times 10^5
\]
先离线，将点全部加入，然后撤销贡献。
考虑容斥，令 \(F_1\) 表示满足条件 \(1\) 的方案，\(F_2\) 表示满足条件 \(2\) 的方案，\(F_3\) 表示都满足的方案。答案即为 \(F_1+F_2-2F_3\)。
取原树的小根重构树 \(T_1\)。则对于 \(x\) 在 \(T_1\) 上的每个祖先 \(y\)，\(y\) 是从 \(x\) 出发的路径上的一个前缀最小值，即满足条件 \(1\)。所以 \(F_1=\sum \text{dep}_1\)。同理取原树的大根重构树 \(T_2\)，\(F_2=\sum \text{dep}_2\)。
两个条件都满足的路径 \(x\to y\) 满足 \(x\) 在 \(T_1\) 上是 \(y\) 的祖先，同时 \(y\) 在 \(T_2\) 上是 \(x\) 的祖先。在 \(T_1\) 上 dfs，维护当前点所有祖先在 \(T_2\) 上的 dfn。\(F_3\) 即当前点在 \(T_2\) 上的子树和。用树状数组维护可以做到 \(\mathcal O(n\log n)\)。
考虑新加入一个点 \(n+i\) 时的贡献。显然有 \(f_2=n+i-1\)。同时 \(f_1=f_3={\text{dep}_1}_{n+i}\)。倒着撤销贡献即可算出全部的答案。
讲个笑话，赛时看错题了，看成了算 \(T_3\)。但是这样反而是顺着正解思路的，所以好像又没完全看错（？
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>const int N = 1e6 + 7;
typedef long long i64;namespace # {int n, m, q;
std::basic_string<int> g[N];struct _bit {int f[N];inline void add(int x, int y) { for(; x <= n; x += x & -x) f[x] += y; }inline int get(int x) { int y = 0; for(; x; x -= x & -x) y += f[x]; return y; }
} B;struct _tree {std::basic_string<int> g[N];int dfn[N], dep[N], siz[N], idx;inline void addedge(int x, int y) { g[x] += y; }void dfs(int u) {dfn[u] = ++idx, siz[u] = 1;;for(int& v: g[u]) {dep[v] = dep[u] + 1, dfs(v);siz[u] += siz[v];}}
} t1, t2;struct _dsu {int fa[N];inline void clear() { memset(fa, 0, 4*(n+1)); }inline int find(int x) {while(x != fa[x]) x = fa[x] = fa[fa[x]];return x; }
} dsu;inline void work() {for(int i = 1; i <= n; ++i) {for(int& v: g[i]) {if(dsu.fa[v]) {t1.addedge(i, dsu.find(v));dsu.fa[dsu.find(v)] = i;}}dsu.fa[i] = i;}dsu.clear();for(int i = n; i >= 1; --i){for(int& v: g[i]) {if(dsu.fa[v]) {t2.addedge(i, dsu.find(v));dsu.fa[dsu.find(v)] = i;}}dsu.fa[i] = i;}t1.dfs(n), t2.dfs(1);
}i64 ans[N], f[N], A, C;
inline void dfs(int u) {A += t1.dep[u] + 1 + t2.dep[u] + 1;B.add(t2.dfn[u], 1);C += B.get(t2.dfn[u] + t2.siz[u] - 1) - B.get(t2.dfn[u] - 1);for(int& v: t1.g[u]) { dfs(v); }B.add(t2.dfn[u], -1);
}inline void main() {std::cin >> n;for(int t = n, x, y; --t; ) {std::cin >> x >> y;g[x] += y, g[y] += x;}std::cin >> q;m = n, n += q;for(int i = m + 1; i <= n; ++i) {int x; std::cin >> x;g[i] += x, g[x] += i;}work();dfs(n);ans[n] = A - 2 * C;for(int i = n; i > m; --i) {f[i] = i - 1 - t2.dep[i]; ans[i-1] = ans[i] - f[i];}for(int i = m; i <= n; ++i) {std::cout << ans[i] << "\n";}
}};int main() {std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);#::main();
}