hdu6162（树链剖分）

hdu6162

题意

给出一颗带点权的树，每次询问一对节点 \((u, v)\)，问 \(u\) 到 \(v\) 的最短路径上所有节点权值在 \([c1, c2]\) 区间内的和。

分析

树链剖分，那么我们只需要处理一个区间内节点权值在 \([c1, c2]\) 之间的和。建一颗线段树，每个节点维护当前区间内所有的点已经排序后的权值，以及前缀和。那么两次二分，前缀和相减就可以快速得到区间内权值在 \([c1, c2]\) 的所有节点的和。

code

#include<bits/stdc++.h>

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, m;

int fa[MAXN]; // fa[v]: v 的父亲

int dep[MAXN]; // dep[v]: v 的深度（根深度为１）

int siz[MAXN]; // : 以 v 为根的子树的节点数

int son[MAXN]; // : 重儿子，siz[u] 为 v　的子节点中 siz　值最大的，那么 u 就是 v 的重儿子

int top[MAXN]; // : 表示 v 所在的重链的顶端节点

int w[MAXN]; // : 表示 v 在线段树中的位置

int num; // 将树映射到线段树上的标号

int cnt, head[MAXN << 1];

struct Edge {

    int to, next;

}edge[MAXN << 1];

void addedge(int u, int v) {

    edge[cnt].to = v;

    edge[cnt].next = head[u];

    head[u] = cnt++;

}

int tre[MAXN]; // 线段树上的点在树上的节点编号

int cost[MAXN];

void dfs(int u) {

    siz[u] = 1; son[u] = 0;

    for(int i = head[u]; ~i; i = edge[i].next) {

        if(edge[i].to != fa[u]) {

            fa[edge[i].to] = u;

            dep[edge[i].to] = dep[u] + 1;

            dfs(edge[i].to);

            if(siz[edge[i].to] > siz[son[u]]) son[u] = edge[i].to;

            siz[u] += siz[edge[i].to];

        }

    }

}

void build_tree(int u, int tp) {

    w[u] = ++num; top[u] = tp;

    if(son[u]) build_tree(son[u], top[u]); // 使重链各边在线段树中呈连续分布

    for(int i = head[u]; ~i; i = edge[i].next) {

        int v = edge[i].to;

        if(v != son[u] && v != fa[u])

            build_tree(v, v);

    }

}

vector<int> v[MAXN << 2];

vector<ll> sum[MAXN << 2];

void pushUp(int rt) {

    v[rt].resize(v[rt << 1].size() + v[rt << 1 | 1].size());

    merge(v[rt << 1].begin(), v[rt << 1].end(), v[rt << 1 | 1].begin(), v[rt << 1 | 1].end(), v[rt].begin());

    sort(v[rt].begin(), v[rt].end());

    ll s = 0;

    for(int i = 0; i < v[rt].size(); i++) {

        s += v[rt][i];

        sum[rt].push_back(s);

    }

}

void build(int l, int r, int rt) {

    v[rt].clear();

    sum[rt].clear();

    if(l == r) {

        v[rt].push_back(cost[tre[l]]);

        sum[rt].push_back(cost[tre[l]]);

        return;

    }

    int m = (l + r) / 2;

    build(lson);

    build(rson);

    pushUp(rt);

}

ll query(int L, int R, int c1, int c2, int l, int r, int rt) {

    if(L <= l && R >= r) {

        int posr = upper_bound(v[rt].begin(), v[rt].end(), c2) - v[rt].begin(); posr--;

        int posl = lower_bound(v[rt].begin(), v[rt].end(), c1) - v[rt].begin(); posl--;

        ll x = posr < 0 ? 0 : sum[rt][posr];

        ll y = posl < 0 ? 0 : sum[rt][posl];

        return x - y;

    }

    int m = (l + r) / 2;

    ll res = 0;

    if(m >= L) res += query(L, R, c1, c2, lson);

    if(m < R) res += query(L, R, c1, c2, rson);

    return res;

}

ll seek(int v, int u, int c1, int c2) {

    int t1 = top[v], t2 = top[u];

    ll res = 0;

    while(t1 != t2) {

        if(dep[t1] < dep[t2]) {

            swap(t1, t2); swap(v, u);

        }

        res += query(w[t1], w[v], c1, c2, 1, n, 1);

        v = fa[t1]; t1 = top[v];

    }

    if(dep[v] > dep[u]) swap(v, u);

    return res + query(w[v], w[u], c1, c2, 1, n, 1);

}

//适用于正整数

template <class T>

inline void scan_d(T &ret) {

    char c; ret=0;

    while((c=getchar())<'0'||c>'9');

    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        memset(head, -1, sizeof head);

        cnt = num = 0;

        for(int i = 1; i <= n; i++) {

            scanf("%d", &cost[i]);

        }

        for(int i = 0; i < n - 1; i++) {

            int u, v;

            scanf("%d%d", &u, &v);

            addedge(u, v);

            addedge(v, u);

        }

        dfs(1);

        build_tree(1, 1);

        for(int i = 1; i <= n; i++) {

            tre[w[i]] = i;

        }

        build(1, n, 1);

        for(int i = 0; i < m; i++) {

            int l, r, c1, c2;

            scan_d(l); scan_d(r); scan_d(c1); scan_d(c2);

            printf("%lld%c", seek(l, r, c1, c2), " \n"[i == m - 1]);

        }

    }

    return 0;

}

巴特西

hdu6162（树链剖分）

hdu6162

题意

分析

code

最新文章

热门文章