问题分析

给定一棵 $n$ 个节点的树，每个节点有一个年龄值 $x_i$。需要处理 $Q$ 次查询，每次查询给出节点 $u$ 和年龄区间 $[L,R]$，求所有年龄在 $[L,R]$ 内的节点到 $u$ 的距离之和。

距离定义为树上两点间路径的边权和。

关键公式

对于查询 $(u, L, R)$，设 $S$ 为年龄在 $[L,R]$ 内的节点集合，则：

$$\text{ans} = \sum_{v \in S} \text{dist}(u,v)$$

利用树的性质可以转化为：

$$\text{ans} = |S| \cdot \text{dist}(root,u) + \sum_{v \in S} \text{dist}(root,v) - 2 \cdot \sum_{v \in S} \text{dist}(root,\text{lca}(u,v)) $$

其中 $root$ 为树根（这里取节点 $1$）。

算法思路

1. 预处理

树链剖分

void dfs1(int u, int f) {
    dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1;
    // 计算深度、父节点、子树大小、重儿子
}

void dfs2(int u, int top) {
    tp[u] = top, dfn[u] = ++pdfn;
    wsum[pdfn] = dis[u];  // DFS序上的边权前缀和
    // 进行重链剖分
}

节点按年龄排序

sort(x + 1, x + 1 + n);  // 按年龄排序，便于区间查询

2. 可持久化数据结构

使用可持久化线段树维护每个年龄前缀对应的路径信息：

struct node {
    int ls, rs;
    ll sum, tim;  // sum: 边权和, tim: 计数
} t[N << 7];

void mdf(int &p, int q, int l, int r, int L, int R) {
    // 在可持久化线段树中插入路径信息
}

对于每个节点 $v$（按年龄排序后），将其到根路径上的所有边插入线段树：

void mdf(int p, int id) {
    while (tp[p] != 1) {
        mdf(pt, pt, 1, n, dfn[tp[p]], dfn[p]);  // 插入重链
        p = fa[tp[p]];
    }
    mdf(pt, pt, 1, n, 1, dfn[p]);  // 插入最后一段
    rt[id] = pt;  // 记录版本根
}

3. 查询处理

年龄区间确定

a = lower_bound(x + 1, x + 1 + n, (ppl){a, 0}) - x;
b = upper_bound(x + 1, x + 1 + n, (ppl){b, 1000000000}) - x - 1;
// 找到年龄在 [a,b] 范围内的节点在排序数组中的区间

距离和计算

ans = 1ll * (b - a + 1) * rdis[u]  // |S| * dist(root,u)
    + pre[b] - pre[a - 1]          // ∑dist(root,v)
    - 2ll * qry(u, a, b);          // -2 * ∑dist(root,lca(u,v))

其中 qry(u, a, b) 计算 $\sum_{v \in S} \text{dist}(root, \text{lca}(u,v))$：

ll qry(int p, int l, int r) {
    ll res = 0;
    while (tp[p] != 1) {
        res += qry(rt[r], rt[l-1], 1, n, dfn[tp[p]], dfn[p]);
        p = fa[tp[p]];
    }
    res += qry(rt[r], rt[l-1], 1, n, 1, dfn[p]);
    return res;
}

复杂度分析

预处理：

树链剖分：$O(n)$

可持久化线段树构建：$O(n \log n)$

每次查询：$O(\log^2 n)$

二分查找年龄区间：$O(\log n)$

树链剖分查询：$O(\log n)$

线段树查询：$O(\log n)$

总复杂度：$O(n \log n + Q \log^2 n)$

关键技巧

1.公式转化：将距离和转化为到根距离的线性组合

2.树链剖分：将树上路径转化为 $O(\log n)$ 个区间

3.可持久化线段树：维护年龄前缀的路径信息

4.离线处理：按年龄排序后批量处理

样例解析

对于样例查询，算法：

1.预处理树结构和节点年龄信息

2.对每个查询，确定年龄区间 $[L,R]$

3.使用公式计算距离和：

• $|S| \cdot \text{dist}(1,u)$
• 加上 $\sum_{v \in S} \text{dist}(1,v)$
• 减去 $2 \cdot \sum_{v \in S} \text{dist}(1,\text{lca}(u,v))$

4.输出结果并更新下一次查询的参数

总结

本题通过巧妙的公式转化和数据结构设计，高效解决了树上带权距离和查询问题：

1.数学转化：利用树的性质简化距离计算

2.树链剖分：高效处理路径查询

3.可持久化数据结构：支持年龄区间查询

4.整体优化：在 $n \leq 1.5 \times 10^5, Q \leq 2 \times 10^5$ 的数据规模下高效运行