Top Cluster 系列：
定义
-
簇（Cluster）：一个连通边集，每个簇有两个界点。
-
界点、内点：两个簇只会在界点处有交，除了界点外其他点为内点。
这两个定义也在 Top Cluster 树分块 解释过，下面用 \(a(u, v)\) 表示含有界点 \(u, v\) 的簇 \(a\)。
簇的两种合并操作
对于两个边集无交、恰好有一个界点重合的簇，可以通过 Compress 操作或 Rake 操作将两者合并成一个新簇。
合并后的新簇的边集为原来两个簇的边集并集。
-
compress 操作：对于两个簇 \(a(u, v), b(v, w)\)，通过 Compress 操作可以将这两个簇合并为簇 \(c(u, w)\)。
-
rake 操作：对于两个簇 \(a(x, w), b(x, v)\)，通过 Compress 操作可以将这两个簇合并为簇 \(c(x, w)\)。
具体如下
Top Tree
定义
对于一棵树的 \(n - 1\) 条边，可以视为 \(n - 1\) 个簇：边集大小为 \(1\)，为对应的边，两个端点为界点。
我们通过不断进行 compress 和 rake 合并操作，将这 \(n - 1\) 个簇逐步合并成一个包含所有边的簇，对应的合并过程对应了一棵树。
定义 Top Tree 为合并过程对应的树。例如：
静态 Top Tree 构建
这里介绍一种方法，先重链剖分。
对于一条重链，先把每个重链上的点 \(u\) 的所有轻儿子的簇通过 rake 操作合并到 \((son_u, u)\) 这个簇上。
然后只剩下重链上的簇了，通过 compress 操作依次合并即可。
为了保证复杂度，需要分治地合并。对于 compress 部分，可以类似于全局平衡二叉树，找到带权中点，注意这里是 Leafy 式的。
对于 rake 部分，同样根据每个轻儿子的子树大小找到带权中点，进行分治。
有分治部分保证，容易发现在 Top Tree 上每跳两次父亲，子树大小至少乘二。
这种构建方式还有一个性质，每个簇的两个界点一定是祖先关系。
点击查看代码
namespace Build {
ll tot, lc[maxn], rc[maxn], siz[maxn], son[maxn]; bool typ[maxn];
vector <ll> nd, nds; ll nowid[maxn], fa[maxn], ft[maxn];
void dfs1(ll u, ll f = 0) {
siz[u] = 1;
for(ll v: to[u])
if(v ^ f) {
dfs1(v, u), siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
ll build(ll l, ll r, bool Typ) { // Typ 表示合并操作为 Compress 还是 Rake
if(l == r) return nd[l];
ll w = nds[r] - (l? nds[l - 1] : 0), lo = l, hi = r - 2;
while(lo <= hi) {
ll mid = lo + hi >> 1;
if((nds[mid] - (l? nds[l - 1] : 0)) * 2 < w) lo = mid + 1;
else hi = mid - 1;
} ll x = lo, id = ++tot; typ[id] = Typ, ft[id] = ft[nd[Typ? r : l]];
return fa[lc[id] = build(l, x, Typ)]
= fa[rc[id] = build(x + 1, r, Typ)] = id;
}
void dfs2(ll u, ll f = 0, bool istp = true) {
nowid[u] = ft[u] = u;
for(ll v: to[u])
if(v != son[u] && v != f) dfs2(v, u);
if(son[u]) {
dfs2(son[u], u, false);
nd.clear(), nds.clear();
nd.pb(nowid[son[u]]), nds.pb(1);
for(ll v: to[u])
if(v != son[u] && v != f)
nd.pb(nowid[v]), nds.pb(siz[v]);
for(ll i = 1; i < nds.size(); i++) nds[i] += nds[i - 1];
nowid[son[u]] = build(0, nd.size() - 1, false);
}
if(istp && son[u]) {
nd.clear(), nds.clear();
for(ll x = u; x; x = son[x])
nd.pb(nowid[x]), nds.pb(siz[x] - siz[son[x]]);
for(ll i = 1; i < nds.size(); i++) nds[i] += nds[i - 1];
nowid[u] = build(0, nd.size() - 1, true);
}
}
} using namespace Build;
Top Tree 分治
构建一棵 Top Tree，然后 DFS。
对于当前簇，找到所有跨越中间界点的所有询问，然后求解。
不难发现这是一个分治的过程，所以称为 Top Tree 分治。
例题
[联合省选 2022] 填树
标算为 \(\mathcal O(n ^ 3)\)，见 题解区。
考虑在移动区间 \([l, l + k]\) 时，所有点的多项式变化次数之和为 \(\mathcal O(n)\)。原来的做法是每次修改后都重新遍历一遍原树，考虑使用 Top Tree 维护。
对于一个簇，维护六个量：
-
所有不包含上界点的路径上所有点权值乘积之和。
-
上界点到下界点路径上所有点权值乘积（不包含上界点）之和。
-
所有点（不包含上界点）到上界点的路径上所有点权值乘积之和。
-
所有点（不包含上界点）到下界点的路径上所有点权值乘积之和。
-
所有包含上界点的路径（路径两端不能是上界点）上所有点权值乘积之和。
-
其中一端为下界点的，所有包含上界点的路径（另一端不能是上界点）上所有点权值乘积之和。
这六者在两种合并操作中是容易求得的，时间复杂度降为 \(\mathcal O(n ^ 2 \log n)\)。
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb push_back
#define i128 __int128
using namespace std;
namespace Read {
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
const inline void rd(T &x) {
char ch; bool neg = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') neg = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(neg) x = -x;
}
} using Read::rd;
const ll maxn = 410, inf = 1e18, mod = 1e9 + 7, iv = mod - mod / 2;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = s * a %mod;
a = a * a %mod, b >>= 1;
} return s;
}
template <class T>
const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
ll n, m, K, l[maxn], r[maxn], rt; vector <ll> to[maxn];
ll h[maxn], ht, op[maxn];
namespace Build {
ll tot, lc[maxn], rc[maxn], siz[maxn], son[maxn]; bool typ[maxn];
vector <ll> nd, nds; ll nowid[maxn], fa[maxn], ft[maxn];
void dfs1(ll u, ll f = 0) {
siz[u] = 1;
for(ll v: to[u])
if(v ^ f) {
dfs1(v, u), siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
ll build(ll l, ll r, bool Typ) {
if(l == r) return nd[l];
ll w = nds[r] - (l? nds[l - 1] : 0), lo = l, hi = r - 2;
while(lo <= hi) {
ll mid = lo + hi >> 1;
if((nds[mid] - (l? nds[l - 1] : 0)) * 2 < w) lo = mid + 1;
else hi = mid - 1;
} ll x = lo, id = ++tot; typ[id] = Typ, ft[id] = ft[nd[Typ? r : l]];
return fa[lc[id] = build(l, x, Typ)]
= fa[rc[id] = build(x + 1, r, Typ)] = id;
}
void dfs2(ll u, ll f = 0, bool istp = true) {
nowid[u] = ft[u] = u;
for(ll v: to[u])
if(v != son[u] && v != f) dfs2(v, u);
if(son[u]) {
dfs2(son[u], u, false);
nd.clear(), nds.clear();
nd.pb(nowid[son[u]]), nds.pb(1);
for(ll v: to[u])
if(v != son[u] && v != f)
nd.pb(nowid[v]), nds.pb(siz[v]);
for(ll i = 1; i < nds.size(); i++) nds[i] += nds[i - 1];
nowid[son[u]] = build(0, nd.size() - 1, false);
}
if(istp && son[u]) {
nd.clear(), nds.clear();
for(ll x = u; x; x = son[x])
nd.pb(nowid[x]), nds.pb(siz[x] - siz[son[x]]);
for(ll i = 1; i < nds.size(); i++) nds[i] += nds[i - 1];
nowid[u] = build(0, nd.size() - 1, true);
}
}
} using namespace Build;
struct Data {
ll a[maxn], b[maxn];
} f[maxn], d[maxn], a[maxn], b[maxn], p[maxn], q[maxn], w[maxn];
const Data operator + (const Data A, const Data B) {
Data C;
for(ll i = 1; i <= m; i++)
C.a[i] = pls(A.a[i], B.a[i]),
C.b[i] = pls(A.b[i], B.b[i]);
return C;
}
const Data operator * (const Data A, const Data B) {
Data C;
for(ll i = m; i; i--)
C.a[i] = A.a[i] * B.a[i] %mod,
C.b[i] = (A.a[i] * B.b[i] + A.b[i] * B.a[i]) %mod;
return C;
}
void compress(ll u) {
f[u] = f[lc[u]] + f[rc[u]] + b[lc[u]] * a[rc[u]] + p[rc[u]] * w[ft[lc[u]]];
d[u] = d[lc[u]] * d[rc[u]];
a[u] = a[lc[u]] + a[rc[u]] * d[lc[u]];
b[u] = b[rc[u]] + b[lc[u]] * d[rc[u]] + q[rc[u]] * w[ft[lc[u]]];
p[u] = p[lc[u]] + a[rc[u]] * q[lc[u]];
q[u] = q[lc[u]] * d[rc[u]];
}
void rake(ll u) {
f[u] = f[lc[u]] + f[rc[u]];
d[u] = d[lc[u]];
a[u] = a[lc[u]] + a[rc[u]];
b[u] = b[lc[u]];
p[u] = p[lc[u]] + p[rc[u]] + a[lc[u]] * a[rc[u]];
q[u] = q[lc[u]] + d[lc[u]] * a[rc[u]];
}
void pushup(ll u) {
if(typ[u]) compress(u);
else rake(u);
}
namespace Lagrange {
ll F[maxn], pre[maxn], suf[maxn], ifac[maxn];
void Init() {
ifac[0] = 1;
for(ll i = 1; i <= m; i++) ifac[i] = ifac[i - 1] * i %mod;
ifac[m] = power(ifac[m]);
for(ll i = m; i; i--) ifac[i - 1] = ifac[i] * i %mod;
}
ll Getval(ll *a, ll x) {
if(x <= 0) return 0;
for(ll i = 1; i <= m; i++) F[i] = pls(a[i], F[i - 1]);
if(x >= 1 && x <= m) return F[x];
ll ret = 0; pre[0] = suf[m + 1] = 1;
for(ll i = 1; i <= m; i++) pre[i] = pre[i - 1] * (x + mod - i) %mod;
for(ll i = m; i; i--) suf[i] = suf[i + 1] * (i + mod - x) %mod;
for(ll i = 1; i <= m; i++)
ret = (ret + pre[i - 1] * suf[i + 1] %mod * ifac[i - 1] %mod
* ifac[m - i] %mod * F[i]) %mod;
return ret;
}
} using Lagrange::Getval;
pir solve(ll k) {
h[0] = -inf; pir res = {};
for(ll i = 1; i <= n; i++) w[i] = {};
for(ll u = 1; u <= tot; u++)
f[u] = d[u] = a[u] = b[u] = p[u] = q[u] = {};
h[ht + 1] = inf;
for(ll i = 0, j = 0; j < ht; ) {
ll st = max(h[j] + k, h[i]), ed = min(h[j + 1] - 1 + k, h[i + 1] - 1);
for(ll u = 1, nowop; u <= n; u++) {
if(i < l[u] || r[u] <= j) nowop = -1;
else if(l[u] <= j && i < r[u]) nowop = 0;
else if(j < l[u] && r[u] <= i) nowop = 1;
else if(j < l[u] && i < r[u]) nowop = 2;
else nowop = 3;
if(nowop == op[u]) continue; op[u] = nowop;
if(nowop == -1) w[u] = {};
if(nowop == 0)
for(ll x = 1; x <= m; x++) {
w[u].a[x] = k + 1;
w[u].b[x] = (2 * x - k + mod) * (k + 1) %mod * iv %mod;
}
if(nowop == 1)
for(ll x = 1; x <= m; x++) {
w[u].a[x] = pls(h[r[u]], mod - h[l[u]]);
w[u].b[x] = (h[r[u]] + h[l[u]] - 1)
* (h[r[u]] - h[l[u]] + mod) %mod * iv %mod;
}
if(nowop == 2)
for(ll x = 1; x <= m; x++) {
w[u].a[x] = pls(x + 1, mod - h[l[u]]);
w[u].b[x] = (x + h[l[u]])
* (x - h[l[u]] + 1 + mod) %mod * iv %mod;
}
if(nowop == 3)
for(ll x = 1; x <= m; x++) {
w[u].a[x] = (h[r[u]] - x + k) %mod;
w[u].b[x] = (x - k + h[r[u]] - 1 + mod)
* (h[r[u]] - x + k + mod) %mod * iv %mod;
}
f[u] = d[u] = a[u] = b[u] = w[u];
for(ll x = fa[u]; x; x = fa[x]) pushup(x);
}
if(i && st <= ed) {
add(res.fi, pls(Getval(f[rt].a, ed),
mod - Getval(f[rt].a, st - 1)));
add(res.se, pls(Getval(f[rt].b, ed),
mod - Getval(f[rt].b, st - 1)));
}
if(h[i + 1] - ed <= h[j + 1] + k - ed) ++i;
else ++j;
} return res;
}
signed main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
rd(n), rd(K); m = n + 3;
memset(op, -1, sizeof op);
for(ll i = 1; i <= n; i++)
rd(l[i]), rd(r[i]), h[++ht] = l[i], h[++ht] = r[i] + 1;
sort(h + 1, h + 1 + ht);
ht = unique(h + 1, h + 1 + ht) - h - 1;
for(ll i = 1; i <= n; i++)
l[i] = lower_bound(h + 1, h + 1 + ht, l[i]) - h,
r[i] = upper_bound(h + 1, h + 1 + ht, r[i]) - h;
for(ll i = 1; i < n; i++) {
ll u, v; rd(u), rd(v);
to[u].pb(v), to[v].pb(u);
}
tot = n; dfs1(1), dfs2(1);
rt = nowid[1], Lagrange::Init();
pir ans1 = solve(K);
pir ans2 = solve(K - 1);
printf("%lld\n%lld\n", pls(ans1.fi, mod - ans2.fi), pls(ans1.se, mod - ans2.se));
return 0;
}