[省选联考 2022] 填树
怎么感觉就是对着机器人那题出的？
考虑暴力怎么做。钦定值域为 \([l, l + K]\) 由于强制选最小值所以要容斥掉 \([l + 1, l + K]\)，然后可以算出每个点可以选的值域区间，那么就是树上前缀积的问题，可以用换根 dp 在 \(O(n)\) 的时间内解决。
注意到每个点的可选值域区间是关于 \(l\) 的分段函数，那么自然的想法就是把分段函数变成普通的额一次函数。之后发现其实就是若干个一次函数的乘积，必然是多项式，所以可以分段插值。
卡常了半天常最后调时限过了。
namespace fafahkvnaslknql {
const int P = 1e9 + 7;
void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
void sub(int &x, int y) {
(x -= y) < 0 ? x += P : 0;
}
int fpow(ll x, int pnt = P - 2) {
ll res = 1;
for(; pnt; pnt >>= 1, x = x * x % P)
if(pnt & 1) res = res * x % P;
return res;
}
const int inv2 = (P + 1) / 2;
const int N = 210;
int n, L, w;
struct info {
int l, r;
int f, g;
int s1, s2;
}a[N];
vector<int> G[N];
int ans1, ans2;
int ml, mr;
int calc(int x) {
return 1ll * x * (x + 1) / 2 % P;
}
void dfs1(int u, int fa) {
ll sf = 1, sg = 0;
for(int v : G[u]) {
if(v == fa) continue;
dfs1(v, u);
sf += a[v].f;
sg += a[v].g;
}
a[u].f = sf % P, a[u].g = sg % P;
a[u].g = (1ll * sg * a[u].s1 + 1ll * sf * a[u].s2) % P;
a[u].f = 1ll * sf * a[u].s1 % P;
}
void dfs2(int u, int fa) {
add(ans1, a[u].f), add(ans2, a[u].g);
const int sf = a[u].f, sg = a[u].g, s1 = a[u].s1, s2 = a[u].s2;
for(int v : G[u]) {
if(v == fa) continue;
if(a[v].f && a[u].f) {
int vd = sf; sub(vd, 1ll * a[v].f * s1 % P);
a[v].g = (a[v].g + 1ll * ((sg - 1ll * a[v].g * s1 - 1ll * a[v].f * s2) % P + P) * a[v].s1 + 1ll * vd * a[v].s2) % P;
a[v].f = (a[v].f + 1ll * vd * a[v].s1) % P;
}
}
for(int v : G[u])
if(v != fa) dfs2(v, u);
}
pair<int, int> solve(int l, int r) {
ans1 = ans2 = 0;
ml = l, mr = r;
for(int i = 1; i <= n; ++i) {
int nl = max(ml, a[i].l), nr = max(nl - 1, min(mr, a[i].r));
a[i].s1 = nr - nl + 1;
a[i].s2 = (calc(nr) - calc(nl - 1));
if(a[i].s2 < 0) a[i].s2 += P;
add(ans1, a[i].s1), add(ans2, a[i].s2);
}
dfs1(1, 0);
dfs2(1, 0);
return mp(ans1, ans2);
}
int x[N << 2], y1[N << 2], y2[N << 2];
int fac[N << 2], ifac[N << 2];
void init() {
fac[0] = ifac[0] = 1;
for(int i = 1; i <= 2 * n + 2; ++i)
fac[i] = 1ll * fac[i - 1] * i % P, ifac[i] = fpow(fac[i]);
}
int d;
int lag1(int v) {
int res = 0, m = d + 1, mul = (v - x[0]) % P;
for(int i = 1; i <= m; ++i)
add(y1[i], y1[i - 1]), mul = 1ll * mul * (v - x[i]) % P;
for(int i = 0; i <= m; ++i) {
int dt = 1ll * y1[i] * mul % P * fpow((v - x[i]) % P) % P
* ifac[i] % P * ifac[m - i] % P;
if((m - i) & 1) sub(res, dt);
else add(res, dt);
}
return res;
}
int lag2(int v) {
int res = 0, m = d + 2, mul = (v - x[0]) % P;
for(int i = 1; i <= m; ++i)
add(y2[i], y2[i - 1]), mul = 1ll * mul * (v - x[i]) % P;
for(int i = 0; i <= m; ++i) {
int dt = 1ll * y2[i] * mul % P * fpow((v - x[i]) % P) % P
* ifac[i] % P * ifac[m - i] % P;
if((m - i) & 1) sub(res, dt);
else add(res, dt);
}
return res;
}
namespace hh {
int dep[N];
void dfs(int u, int fa) {
for(int v : G[u]) {
if(v == fa) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
pii b[N];
int solve() {
dfs(1, 0);
int pos = 0;
for(int i = 1; i <= n; ++i)
if(dep[i] > dep[pos]) pos = i;
dep[pos] = 0, dfs(pos, 0);
for(int i = 1; i <= n; ++i)
if(dep[i] > dep[pos]) pos = i;
int mx = 0;
for(int i = 1; i <= n; ++i)
b[i] = mp(a[i].l, -a[i].r);
sort(b + 1, b + n + 1);
vector<int> vec;
for(int i = 1; i <= n; ++i) {
mx = max(mx, (int)(lower_bound(vec.begin(), vec.end(), a[i].r + 1) - vec.begin()));
vec.insert(lower_bound(vec.begin(), vec.end(), a[i].r), a[i].r);
}
return min(dep[pos], mx);
}
}
void main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
double st = clock();
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> L;
init();
int mn = 1e9;
for(int i = 1; i <= n; ++i)
cin >> a[i].l >> a[i].r, w = max(w, a[i].r), mn = min(mn, a[i].l);
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[u].eb(v), G[v].eb(u);
}
d = hh::solve();
int ans1 = 0, ans2 = 0;
vector<int> vec;
for(int i = 1; i <= n; ++i)
vec.emplace_back(max(mn, a[i].l - L)), vec.eb(a[i].l), vec.eb(a[i].r - L + 1), vec.eb(a[i].r + 1);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int _ = 0; _ + 1 < sz(vec); ++_) {
int l = vec[_], r = vec[_ + 1];
if(r - l <= d + 3) {
for(int i = l; i < r; ++i) {
auto r1 = solve(i, i + L), r2 = solve(i + 1, i + L);
add(ans1, r1.first), sub(ans1, r2.first);
add(ans2, r1.second), sub(ans2, r2.second);
}
} else {
int m = d + 2;
for(int i = l; i <= l + m; ++i) {
auto r1 = solve(i, i + L), r2 = solve(i + 1, i + L);
x[i - l] = i;
sub(y1[i - l] = r1.first, r2.first);
sub(y2[i - l] = r1.second, r2.second);
}
add(ans1, lag1(r - 1)), add(ans2, lag2(r - 1));
}
}
ans1 = 1ll * ans1 * inv2 % P, ans2 = 1ll * ans2 * inv2 % P;
cout << ans1 << '\n' << ans2 << '\n';
double ed = clock();
cerr << "Time = " << (ed - st) / CLOCKS_PER_SEC << endl;
}
}
int main() {
fafahkvnaslknql :: main();
}