瞻仰遗迹，沐浴圣光。
Description
给出一颗 \(n\) 个节点的树，以及 \(m\) 条链，求有多少对链满足其交的边数 \(\geq k\)。
这个题其实有一个 Hint 是 CF1486F，比这个简单了很多倍。
Solution
我们考虑用 \((s, t, lca)\) 来表示一条 \(s \to t (dfn_s < dfn_t)\) 的链，其中 \(lca\) 表示 \((s, t)\) 的 LCA。
然后我们考虑两条链 \(c_1\) 和 \(c_2\)。
- \(lca_1 \not = lca_2\) ：
钦定 \(dep_{lca_1} < dep_{lca_2}\)。
这个我们发现肯定是类似大链上挂小链，考虑套路，我们考虑在小链上计算贡献，具体来说，我们可以钦定交的那一个端点在 \(c_2\) 上的一端，然后我们向那一端的向下走 \(k\) 步，其子树内的端点就必然可以交上 \(\geq k\) 条边。
- \(lca_1 = lca_2\)：
这个情况有很多个 case。
第一个 case 两个方向都有交。
这个比较好做，先钦定自己有一边是交完的那么我们枚举那个交完的，减去其贡献剩下的边数，我们只需要向另一端走 \(k - \Delta\) 步到 \(p\) 就好了，再统计交完的链中另一端在 \(p\) 的子树中就好了，这个可以自底向上来做，使用动态开点线段树对于相应 LCA 统计贡献就好了。
具体实现是枚举 \(s\)，然后插入对应的 \(t\) 就好了。
第二个 case 是 \((s1, s2)\) 和 \((t1, t2)\) 交在一起。
这个我们可以考虑枚举 \((s1, s2)\) 的 LCA，一种想法是启发式合并虚树，另一种想法就是树上启发式合并。我们知道贡献是 \(x \to lca_1\) 这一段以及 \(lca_1 \to LCA(t_1, t_2)\) 这一段。我们可以启发式合并的时候按照刚才的想法，向 \(t_1\) 走 \(k - \Delta\) 步，再统计在其子树内的对应端点数。仍然还是动态开点线段树。
第三个 case 是 \((s_1, t_1)\) 和 \((s_2, t_2)\) 并在了一段。
这个比较简单，只需要插入 \(s\) 这个端点，查询向 \(t\) 走 \(k\) 步的子树内端点个数就好了，他还是动态开点线段树。
复杂度大概是 \(O(n\log^2 n)\)。
Implement
- 注意到动态开点线段树只用开一颗，因为各个 case 都互不影响。
- 有一点点细节，还是比较清新的。
// LUOGU_RID: 144464014
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
using namespace std;
const int _ = 1.5e5 + 5;
int read() {
int X = 0;
char ch = 0, w = 0;
while (ch < 48 || ch > 57)ch = getchar(), w |= (ch == '-');
while (ch >= 48 && ch <= 57)X = X * 10 + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
int n, m, k, dfc;
int pa[_][20], dep[_], dfn[_], tr[_], sz[_], son[_], val[_];
vector <int> e[_];
long long ans;
void dfs1 (int x, int fa) {
dep[x] = dep[fa] + 1, sz[x] = 1, pa[x][0] = fa;
dfn[x] = ++ dfc, tr[dfc] = x;
rep(i, 1, 19) pa[x][i] = pa[pa[x][i - 1]][i - 1];
for (int y : e[x])
if (y ^ fa) {
dfs1(y, x);
sz[x] += sz[y];
if (sz[son[x]] < sz[y]) son[x] = y;
}
}
int LCA (int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
rep(i, 0, 19) if (d & (1 << i)) x = pa[x][i];
if (x == y) return x;
per(i, 19, 0) if (pa[x][i] ^ pa[y][i]) x = pa[x][i], y = pa[y][i];
return pa[x][0];
}
int kthanc (int x, int k) {
rep(i, 0, 19) if (k & (1 << i)) x = pa[x][i];
return x;
}
struct chain { int s, t, lca; } ;
vector <chain> vs[_], vm[_];
int rt[_];
template <int S>
struct SegMentTree {
int tot, lc[S], rc[S], sz[S];
SegMentTree() {
tot = 0, memset(sz, 0, sizeof(sz));
memset(lc, 0, sizeof(lc)), memset(rc, 0, sizeof(rc));
}
void insert (int &x, int l, int r, int v, int k) {
if(!x) x = ++ tot; sz[x] += k;
if (l == r) return ;
int mid = (l + r) >> 1;
v <= mid ? insert(lc[x], l, mid, v, k) : insert(rc[x], mid + 1, r, v, k);
}
int query (int x, int l, int r, int ql, int qr) {
if (!x) return 0;
if (ql <= l && r <= qr) return sz[x];
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res += query(lc[x], l, mid, ql, qr);
if (qr > mid) res += query(rc[x], mid + 1, r, ql, qr);
return res;
}
int merge (int x, int y) {
if (!x || !y) return x | y;
sz[x] += sz[y];
lc[x] = merge(lc[x], lc[y]), rc[x] = merge(rc[x], rc[y]);
return x;
}
} ;
SegMentTree <_ * 256> T;
void dfs3 (int x, int fa) {
for (int y : e[x]) if (y ^ fa) dfs3(y, x), rt[x] = T.merge(rt[x], rt[y]);
T.insert(rt[x], 1, n, dfn[x], val[x]);
for (auto [u, v, lca] : vm[x])
T.insert(rt[x], 1, n, dfn[u], -1), T.insert(rt[x], 1, n, dfn[v], -1);
for (auto [u, v, lca] : vm[x]) {
if (dep[u] - dep[x] >= k) {
u = kthanc(u, dep[u] - dep[x] - k);
ans += T.query(rt[x], 1, n, dfn[u], dfn[u] + sz[u] - 1);
}
if (dep[v] - dep[x] >= k) {
v = kthanc(v, dep[v] - dep[x] - k);
ans += T.query(rt[x], 1, n, dfn[v], dfn[v] + sz[v] - 1);
}
}
}
void dfs4 (int x, int fa, int t) {
for (int y : e[x]) if (y ^ fa && y ^ son[x]) dfs4(y, x, 0);
if (son[x]) dfs4(son[x], x, 1);
for (auto [u, v, lca] : vs[x]) {
int p = v;
if (dep[u] + dep[v] - 2 * dep[lca] >= k) {
v = kthanc(v, dep[v] - dep[lca] - max(0, k - dep[u] + dep[lca]));
ans += T.query(rt[lca], 1, n, dfn[v], dfn[v] + sz[v] - 1);
}
T.insert(rt[lca], 1, n, dfn[p], 1);
}
for (int y : e[x]) {
if (y == fa || y == son[x]) continue ;
rep(id, dfn[y], dfn[y] + sz[y] - 1)
for (auto [u, v, lca] : vs[tr[id]]) {
if (dep[lca] > dep[x] || dep[x] + dep[v] - 2 * dep[lca] < k) continue ;
v = kthanc(v, dep[v] - dep[lca] - max(0, k - dep[x] + dep[lca]));
ans += T.query(rt[lca], 1, n, dfn[v], dfn[v] + sz[v] - 1);
}
rep(id, dfn[y], dfn[y] + sz[y] - 1) {
for (auto [u, v, lca] : vs[tr[id]]) {
T.insert(rt[lca], 1, n, dfn[v], 1);
}
}
}
if (!t) {
rep(id, dfn[x], dfn[x] + sz[x] - 1)
for (auto [u, v, lca] : vs[tr[id]]) {
T.insert(rt[lca], 1, n, dfn[v], -1);
}
}
}
int main () {
n = read(), m = read(), k = read();
rep(i, 1, n - 1) {
int x = read(), y = read();
e[x].push_back(y), e[y].push_back(x);
}
dfs1(1, 0);
rep(i, 1, m) {
int x = read(), y = read(), lca;
lca = LCA(x, y), val[x] ++, val[y] ++;
if (dfn[x] > dfn[y]) swap(x, y);
vs[x].push_back({x, y, lca}), vm[lca].push_back({x, y, lca});
}
dfs3(1, 0);
rep(i, 1, n) rt[i] = 0;
dfs4(1, 0, 0);
rep(i, 1, n) {
for (auto [x, y, z] : vm[i]) T.insert(rt[i], 1, n, dfn[x], 1);
for (auto [x, y, z] : vm[i]) {
if (dep[y] - dep[i] >= k) {
y = kthanc(y, dep[y] - dep[i] - k);
ans += T.query(rt[i], 1, n, dfn[y], dfn[y] + sz[y] - 1);
}
}
}
cout << ans << endl;
return 0;
}
/*
13 8 3
7 6
9 11
5 6
11 3
9 7
2 12
4 3
1 2
5 8
6 13
5 10
3 1
10 4
10 11
8 11
4 9
2 5
3 5
7 3
8 10
*/