Chlience

【题解】LOJ 2116 「HNOI2015」开店
Problem给定一棵树,其中点有点权,边有边权每次询问点权在 $[l,r]$ 内的点到 $u$ 的距离和是多少T...
扫描右侧二维码阅读全文
11
2019/02

【题解】LOJ 2116 「HNOI2015」开店

Problem

给定一棵树,其中点有点权,边有边权
每次询问点权在 $[l,r]$ 内的点到 $u$ 的距离和是多少

Thought

看起来是很经典的题啊

统计某个点距离和什么的一般来讲会自然的想到动态点分治吧

对于点分树上的每一个点,我们维护三个值:

  1. 点分树子树中节点到该点距离
  2. 点分树子树中节点到该点父亲节点距离

至于怎么取 $[l,r]$ 区间,可以用点权为关键字排序后做前缀和 lower_bound

然后就是动态点分治裸题了

说起来简单码起来难,不如树链剖分啊...

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 150010;
const int M = 200010;
int n, m, A;
int a[N];
struct Edge {
    int t, n, w;
}e[N << 1];
int head[N], tot;
int headE[N], totE;

int dep[N];
int fa[N][22];
int dis[N][22];

int siz[N], max_siz[N];
int rt;
int pre[N];
bool vis[N];

vector <int> son[N];

struct Node {
    int key;
    long long sum;
    bool operator < (const Node a) const {
        return key < a.key;
    }
    void operator += (const Node a) {
        sum += a.sum;
    }
};
vector <Node> sumDis[N], sumDisFa[N], sumDisPro[N], sumDisFaPro[N]; 

void addedge(int u, int v, int w) {
    e[++ tot] = {v, head[u], w};
    head[u] = tot;
}

void dfs(int x) {
    dep[x] = dep[fa[x][0]] + 1;
    for(int i = 1; i <= 20; ++ i) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        dis[x][i] = dis[x][i - 1] + dis[fa[x][i - 1]][i - 1];
    }
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa[x][0]) continue;
        fa[e[i].t][0] = x;
        dis[e[i].t][0] = e[i].w;
        dfs(e[i].t);
    }
}

int getDis(int x, int y) {
    int ans = 0;
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; -- i)
        if(dep[fa[x][i]] >= dep[y]) {
            ans += dis[x][i];
            x = fa[x][i];
        }
    if(x == y) return ans;
    for(int i = 20; i >= 0; -- i)
        if(fa[x][i] != fa[y][i]) {
            ans += dis[x][i];
            ans += dis[y][i];
            x = fa[x][i];
            y = fa[y][i];
        }
    ans += dis[x][0];
    ans += dis[y][0];
    return ans;
}

void getSize(int x, int pre) {
    siz[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == pre || vis[e[i].t]) continue;
        getSize(e[i].t, x);
        siz[x] += siz[e[i].t];
    }
}

void getRoot(int x, int pre, int sum_siz) {
    max_siz[x] = sum_siz - siz[x];
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == pre || vis[e[i].t]) continue;
        getRoot(e[i].t, x, sum_siz);
        max_siz[x] = max(max_siz[x], siz[e[i].t]);
    }
    if(!rt || max_siz[x] < max_siz[rt]) rt = x;
}

void getSum(int x, int pre, int p) {
    sumDis[p].push_back({a[x], getDis(x, p)});
    if(:: pre[p]) sumDisFa[p].push_back({a[x], getDis(x, :: pre[p])});
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == pre || vis[e[i].t]) continue;
        getSum(e[i].t, x, p);
    }
}
void build(int x) {
    vis[x] = 1;

    for(int i = head[x]; i; i = e[i].n) {
        if(vis[e[i].t]) continue;
        rt = 0;
        getSize(e[i].t, x);
        getRoot(e[i].t, x, siz[e[i].t]);

        int root = rt;
        pre[root] = x;
        build(root);
    }
    vis[x] = 0;
    getSum(x, pre[x], x);
    sort(sumDis[x].begin(), sumDis[x].end());
    sort(sumDisFa[x].begin(), sumDisFa[x].end());
    for(int i = 1; i < sumDis[x].size(); ++ i)
        sumDis[x][i] += sumDis[x][i - 1];
    for(int i = 1; i < sumDisFa[x].size(); ++ i)
        sumDisFa[x][i] += sumDisFa[x][i - 1];
}

long long cal(int x, int l, int r) {
    int oldx = x, pos;
    long long ans = 0;
    do {
        long long Dis = getDis(x, oldx);
        pos = upper_bound(sumDis[x].begin(), sumDis[x].end(), Node{r, 0}) - sumDis[x].begin();
        if(pos) ans += sumDis[x][pos - 1].sum;
        ans += Dis * pos;
        pos = upper_bound(sumDis[x].begin(), sumDis[x].end(), Node{l, 0}) - sumDis[x].begin();
        if(pos) ans -= sumDis[x][pos - 1].sum;
        ans -= Dis * pos;
        if(pre[x]) {
            Dis = getDis(pre[x], oldx);
            pos = upper_bound(sumDisFa[x].begin(), sumDisFa[x].end(), Node{r, 0}) - sumDisFa[x].begin();
            if(pos) ans -= sumDisFa[x][pos - 1].sum;
            ans -= Dis * pos;
            pos = upper_bound(sumDisFa[x].begin(), sumDisFa[x].end(), Node{l, 0}) - sumDisFa[x].begin();
            if(pos) ans += sumDisFa[x][pos - 1].sum;
            ans += Dis * pos;
        }
        x = pre[x];
    }while(x);
    return ans;
}

int main() {
    n = read(); m = read(); A = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    for(int i = 1; i < n; ++ i) {
        int a = read(), b = read(), c = read();
        addedge(a, b, c);
        addedge(b, a, c);
    }
    dfs(1);
    getSize(1, 0);
    getRoot(1, 0, siz[1]);
    int root = rt;
    build(root);

    long long ans = 0;
    for(int i = 1; i <= m; ++ i) {
        int u = read();
        long long a = ans + read(), b = ans + read();
        int L = min(a % A, b % A) - 1;
        int R = max(a % A, b % A);
        ans = cal(u, L, R);
        printf("%lld\n", ans);
    }
    return 0;
}
Last modification:February 11th, 2019 at 08:18 pm

Leave a Comment