开店问题

解题思路

本题有若干个询问，每次给出一个点和一个年龄范围，要求所有在年龄范围内的点到目标点的距离之和。

本题是可以用点分治的方法来做，对于每一个询问，可以分成两类来看，如果 $u$ 在某一个子树中，其余的点如果和 $u$ 在同一棵子树中，我们可以递归到子树中去做。如果其余的点和 $u$ 不在同一棵子树中，那么我们可以用归并的方式去做。

然后可以发现每一个询问都不会修改树的形态，因此对于每一次询问，如果我们都用点分治的方法去做的话，那么每次选择的重心都是完全一样的，因此我们可以通过一次预处理，将选重心的过程存下来，这样每次询问都可以直接复用。这里就要用点分树来存储所有重心。

最开始是一整棵树，也就是一整个区间，则每次选重心的过程就是将区间拆分成若干个不相交的子区间，最多会有 $logn$ 层，而每个询问的 $u$ 最多属于其中的 $logn$ 层，那么最终的答案其实就是 $u$ 每一层的方案相加。比如第一层，也就是整棵树的时候，如果 $u$ 在某一棵子树中，那么同一层内的距离和相当于是跨过重心的所有路径的距离之和。此时我们就求出了和 $u$ 在不同子树内的路径的距离之和，剩下的都是和 $u$ 在同一子树内的路径，这些路径我们可以递归到下一层去继续求。而此时我们其实只是继续去递归 $u$ 所在的子树，这颗子树独立出来后又是一个和原先相同的结构，有一个重心，$u$ 都在某一棵子树中，然后继续求和 $u$ 在不同子树中的路径，也就是同一层的所有路径。依此类推继续将向 $u$ 所在的子树递归。直到 $u$ 所在的连通块只有一个点或 $u$ 是重心为止。此时我们就不需要再递归，只需要求一个所有子树中每个点到 $u$ 的路径和即可。

以上的过程中可以发现，每求一次都会降一层，一共只有 $logn$ 层，所以最多只会递归 $logn$ 次，这样一定可以把所有方案求出来。

接下来我们还需要快速处理两个操作。一个是快速求出 $u$ 和不同子树中所有点的距离之和。一个是快速求出 $u$ 和所有儿子节点的距离之和。

本题有一个性质，所有点的度数都 $\leq 3$，因此每个点的子树最多只有三个，因此对于第一个问题，我们可以暴力枚举另外两棵子树，对于每颗子树，我们其实就是要求这棵子树中所有年龄在 $L \sim R$ 之间的所有点到 $u$ 的距离之和，由于所有这样的路径都是经过重心的，所以我们可以将这些路径分成两段，一段是重心到 $u$，一段是重心到子树中每个点的距离。整段路径的距离就是这两段路径的距离之和，而第一段对于每条路径都是固定的，一共几条路径，第一段就要加上几次，而路径的数量取决于当前子树中有多少个年龄在 $L \sim R$ 之间的点。这里也可以比较暴力的做，我们将当前子树中的所有年龄都存到重心里，然后将这些年龄排个序，那么现在就相当于在一个有序数组中求某个范围内的数的个数，这个用二分来求。而第二段是要求当前子树中所有年龄在 $L \sim R$ 之间的点到重心的距离和，和第一段一样，我们在存所有点的信息的时候存两个信息，一个是这个点的年龄，另一个是这个点到重心的距离。然后我们将所有点按照年龄从小到大排序，此时某一个年龄范围的所有点的距离和其实就是求一个区间和，因此我们可以预处理一下前缀和，然后二分 $L \sim R$ 的两个端点，然后求一个区间和即可。二分是 $O(logn)$ 的，求区间和是 $O(1)$ 的，因此每次都是 $logn$ 的复杂度。

通过以上这个思路，对于第二个问题也可以用类似的方式来求。$u$ 的儿子也最多只有 $3$ 个，因此可以每个儿子单独求，而每个儿子就是求在 $L \sim R$ 之间所有点到 $u$ 的距离和，$u$ 就是此时的重心，因此就是求 $L \sim R$ 之间所有点到重心的距离和，就用上面同样的方法来求即可。

接下来我们还需要将这颗点分树建出来，其实就是考虑一下需要哪些信息，首先对于每个重心，需要存储他每个子树中的所有节点的年龄和到重心的距离。然后对于每个 $u$，我们需要快速直到他每一层的重心是谁，方便我们去向着 $u$ 去递归。

综上所述，就是整个问题的全部思路。

注意，我们考虑的时候只考虑了重心的所有子节点和 $u$ 的距离，没有考虑重心，如果重心的年龄也在范围内，还需要单独算上。

然后考虑一下复杂度，由于每一层我们都需要存下所有点的信息，一共 $logn$ 层，因此空间复杂度是 $O(nlogn)$。而每一层时间的上限都是一个排序，因此时间复杂度就是 $O(nlog^2n)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 150010, M = N * 2;

int n, m, A;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int age[N]; //存储每个节点的年龄
bool st[N]; //记录每个节点是否被删掉
struct Father
{
    int u, num; //记录每个节点在它所在的子树的重心 u 的第 num 个儿子中
    LL dist; //记录每个节点到重心 u 的距离
}; //存储每个节点关于父节点的信息
vector<Father> f[N]; //对于每个节点都要存储若干个父节点的信息
struct Son
{
    int age; //记录当前节点的年龄
    LL dist; //记录当前节点到重心的距离
    bool operator< (const Son &t) const
    {
        return age < t.age;
    }
};
vector<Son> son[N][3]; //对于每个节点最多有 3 棵子树，需要存储每棵子树中所有节点的信息

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int get_size(int u, int fa) //求 u 所在子树的大小
{
    if(st[u]) return 0; //如果 u 已经被删掉，直接返回
    int res = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) //求重心
{
    if(st[u]) return 0; //如果 u 已经被删掉，直接返回
    int sum = 1, ms = 0; //记录 u 所在子树大小，ms 表示所有子树的最大节点数
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if(ms <= tot / 2) wc = u;
    return sum;
}

//dist 表示 u 到重心的距离
//wc 表示重心
//k 表示 u 是 wc 的第几棵子树
void get_dist(int u, int fa, LL dist, int wc, int k, vector<Son> &p) //将 u 的第 k 个子树中所有节点存储 p
{
    if(st[u]) return; //如果 u 已经被删掉，直接返回
    f[u].push_back({wc, k, dist}); //存储重心信息
    p.push_back({age[u], dist}); //存储子节点信息
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        get_dist(j, u, dist + w[i], wc, k, p);
    }
}

void calc(int u) //构建点分树
{
    if(st[u]) return; //如果 u 已经被删掉，直接返回
    get_wc(u, -1, get_size(u, -1), u); //求重心
    st[u] = true; //将重心删掉

    for(int i = h[u], k = 0; i != -1; i = ne[i]) //k 表示当前子树的编号
    {
        int j = e[i];
        if(st[j]) continue; //如果 j 已经被删掉，说明它已经作为重心出现在前面，不再考虑
        auto &p = son[u][k]; //当前子树对应的容器
        p.push_back({-1, 0}), p.push_back({A + 1, 0}); //加入两个哨兵，防止边界情况
        get_dist(j, -1, w[i], u, k, p); //将子树中所有点存储对应的容器中
        k++;
        sort(p.begin(), p.end()); //将子树中所有节点按照年龄排序
        for(int i = 1; i < p.size(); i++) p[i].dist += p[i - 1].dist; //预处理距离的前缀和
    }

    for(int i = h[u]; i != -1; i = ne[i]) calc(e[i]); //递归构建每棵子树
}

LL query(int u, int l, int r) //计算所有年龄在 [l, r] 之间的点到 u 的距离之和
{
    LL res = 0; //记录答案
    for(int i = 0; i < f[u].size(); i++) //枚举 u 所在的每一层
    {
        auto &t = f[u][i]; //记录当前层的重心
        int g = age[t.u];
        if(g >= l && g <= r) res += t.dist; //如果重心也在年龄范围内，单独考虑
        for(int j = 0; j < 3; j++) //枚举重心的所有子树
        {
            if(j == t.num) continue; //和 u 在同一棵子树的节点不用考虑
            auto &p = son[t.u][j]; //当前子树的所有节点
            if(p.empty()) continue; //如果当前子树为空，直接跳过
            int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
            int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin() - 1;
            res += t.dist * (b - a + 1) + p[b].dist - p[a - 1].dist; //计算当前层和 u 不在同一子树的所有路径的距离和
        }
    }

    for(int i = 0; i < 3; i++) //枚举 u 的所有子树
    {
        auto &p = son[u][i]; //当前子树的所有节点
        if(p.empty()) continue; //如果当前子树为空，直接跳过
        int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
        int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin() - 1;
        res += p[b].dist - p[a - 1].dist; //计算当前子树中所有路径的距离和
    }

    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m, &A);
    for(int i = 1; i <= n; i++) scanf("%d", &age[i]);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); //无向边
    }

    calc(1); //构建点分树

    LL res = 0; //记录当前的答案
    while(m--)
    {
        int u, a, b;
        scanf("%d%d%d", &u, &a, &b);
        int l = (a + res) % A, r = (b + res) % A;
        if(l > r) swap(l, r);
        res = query(u, l, r); //查询当前询问
        printf("%lld\n", res);
    }

    return 0;
}