题解 CF1260F 【Colored Tree】

· · 题解

请到博客查看

首先设根为 1，设 \text{dep}(x) 为 x 的深度（\text{dep}(1) = 0），设 \text{dis}(x,y), \text{lca}(x,y) 分别为 x,y 的距离和最近公共祖先，显然有 \text{dis}(x,y) = \text{dep}(x) + \text{dep}(y) - 2\text{dep}(\text{lca}(x,y))。

再设 v(x,c) = [l_x \le c \le r_x]，g(x) = r_x - l_x + 1，p = \prod_{i = 1} ^ n g(i)。

对于两个点 x,y 和一个颜色 c，其对答案的贡献为

\begin{aligned} ans &= [l_x \le c \le r_x][l_y \le c \le r_y]\text{dis}(x,y)\prod_{z \ne x,y}(r_z - l_z + 1) \\ &= pv(x,c)v(y,c)(\text{dep}(x) + \text{dep}(y) - 2\text{dep}(\text{lca}(x,y)))\frac{1}{g(x)g(y)} \end{aligned}

首先考虑

A = v(x,c)v(y,c)(\text{dep}(x) + \text{dep}(y))\frac{1}{g(x)g(y)}

注意到，对于一个点 x 和一个颜色 c，其对 A 贡献为

v(x,c)\text{dep}(x)(\sum_{v(y,c)}\frac{1}{g(x)g(y)} - \frac{1}{g^2(x)})

则

\begin{aligned} A &= \sum_{v(x,c)}\text{dep}(x)(\sum_{v(y,c)}\frac{1}{g(x)g(y)} - \frac{1}{g^2(x)}) \\ &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g(x)}\sum_{v(x,c)}\frac{1}{g(x)}-\sum_{v(x,c)}\frac{\text{dep}(x)}{g^2(x)} \end{aligned}

显然可以把 c 从小到大扫一遍，同时维护

\begin{aligned} A_1 &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g(x)} \\ A_2 &= \sum_{v(x,c)}\frac{1}{g(x)} \\ A_3 &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g^2(x)} \end{aligned}

接下来考虑

B = v(x,c)v(y,c)\text{dep}(\text{lca}(x,y))\frac{1}{g(x)g(y)}

设 s(x) 表示 x 对 B 的贡献，S(x) 表示 x 的所有祖先的 s 之和。

注意到当我们加入一个点 x 时，如果将 x 的所有祖先的 s 全都加上 g(x)，那么对于一个 y，其对 B 的贡献 = \frac{S(y) - s(1)}{g(y)}。

树剖 + 树状数组即可。

总时间复杂度 \mathcal O(n \log^2 n)。

const int N = 1e5 + 7;
int n, C, l[N], r[N], d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
modint g[N], vg[N], p, vp, now, A1, A2, A3, ans, c1[N], c2[N];
vi e[N], L[N], R[N];

void dfs(int x) {
    s[x] = 1;
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (y == f[x]) continue;
        d[y] = d[x] + 1;
        f[y] = x;
        dfs(y);
        s[x] += s[y];
        if (s[y] > s[son[x]]) son[x] = y; 
    }
}

void dfs(int x, int p) {
    top[x] = p;
    dfn[x] = ++num;
    rnk[num] = x;
    if (!son[x]) return;
    dfs(son[x], p);
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (y == f[x] || y == son[x]) continue;
        dfs(y, y);
    }
}

inline void add(modint *c, int x, modint k) {
    while (x <= n + 1) c[x] += k, x += x & -x;
}

inline modint ask(modint *c, int x) {
    modint ret = 0;
    while (x) ret += c[x], x -= x & -x;
    return ret;
}

inline void Add(int x, modint k) {
    while (x) {
        add(c1, dfn[top[x]], k);
        add(c1, dfn[x] + 1, -k);
        add(c2, dfn[top[x]], k * dfn[top[x]]);
        add(c2, dfn[x] + 1, -k * (dfn[x] + 1));
        x = f[top[x]];
    }
}

inline modint Ask(int x) {
    modint ret = -(ask(c1, 1) * 2 - ask(c2, 1));
    while (x) {
        ret += ask(c1, dfn[x]) * (dfn[x] + 1) - ask(c2, dfn[x]);
        ret -= ask(c1, dfn[top[x]] - 1) * dfn[top[x]] - ask(c2, dfn[top[x]] - 1);
        x = f[top[x]];
    }
    return ret;
}

int main() {
    rd(n), p = 1;
    for (int i = 1; i <= n; i++) {
        rd(l[i]), rd(r[i]);
        g[i] = r[i] - l[i] + 1;
        vg[i] = g[i] ^ -1;
        p *= g[i];
        C = max(C, r[i]);
        L[l[i]].pb(i), R[r[i]].pb(i);
    }
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    vp = p ^ -1;
    dfs(1);
    dfs(1, 1);
    for (int c = 1; c <= C; c++) {
        for (ui i = 0; i < L[c].size(); i++) {
            int x = L[c][i];
            A1 += d[x] * vg[x];
            A2 += vg[x];
            A3 += d[x] * vg[x] * vg[x];
            now += Ask(x) * vg[x];
            Add(x, vg[x]);
        }
        ans += A1 * A2 - A3 - 2 * now;
        for (ui i = 0; i < R[c].size(); i++) {
            int x = R[c][i];
            A1 -= d[x] * vg[x];
            A2 -= vg[x];
            A3 -= d[x] * vg[x] * vg[x];
            Add(x, -vg[x]);
            now -= Ask(x) * vg[x];
        }
    }
    print(ans * p);
    return 0;
}