【链接】h在这里写链接

【题意】

给你一棵树,每个节点上都有一个权值.

然后给你m个询问,每个询问(x,y,a,b);

表示询问x->y这条路径上权值在[a,b]范围内的节点的权值和.

【题解】

树链剖分题。

在树链上建一个线段树,线段树的每个节点存3个值,max[i],min[i],sum[i]分别表示这个区间里面的数的最大值、最小值、以及权值和。

然后在线段树上做查找(a,b)范围内的数的权值和。

如果该节点在路径上,那么如果a<=min[i] && max[i] <= b的话,直接返回sum[i],否则如果不在范围里,直接范围0(肯定不在的话);

如果没办法确定在不在,则继续往下走。

【错的次数】

【反思】

关了同步之后,不能用puts("");

【代码】

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int N = 1e5;

int n, m, c[N + 10], uppest[N + 10], idx[N + 10], cnt, sz[N + 10], dep[N + 10];

long long sum[(N + 10) << 2];

int mi[(N + 10) << 2], ma[(N + 10) << 2], a, b, fat[N + 10];

vector <int> g[N + 10];

void dfs1(int x, int fa) {

    sz[x] = 1;

    for (int y : g[x]) {

        if (y == fa) continue;

        dep[y] = dep[x] + 1;

        dfs1(y, x);

        sz[x] += sz[y];

        fat[y] = x;

    }

}

void dfs2(int x, int chain) {

    idx[x] = ++cnt;

    uppest[x] = chain;

    int ma = 0;

    for (int y : g[x]) {

        if (dep[y] > dep[x] && sz[y] > sz[ma]) {

            ma = y;

        }

    }

    if (ma == 0) return;

    dfs2(ma, chain);

    for (int y : g[x])

        if (dep[y] > dep[x] && y != ma)

            dfs2(y, y);

}

void updata(int pos, int x, int l, int r, int rt) {

    if (l == r) {

        mi[rt] = ma[rt] = x;

        sum[rt] = x;

        return;

    }

    int m = (l + r) >> 1;

    if (pos <= m)

        updata(pos, x, l, m, rt << 1);

    else

        updata(pos, x, m + 1, r, rt << 1 | 1);

    ma[rt] = max(ma[rt << 1 | 1], ma[rt << 1]);

    mi[rt] = min(mi[rt << 1 | 1], mi[rt << 1]);

    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

}

void pre() {

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

        updata(idx[i], c[i], 1, n, 1);

}

long long get_ans(int L, int R, int l, int r, int rt) {

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

        if (ma[rt] < a) return 0;

        if (mi[rt] > b) return 0;

        if (a <= mi[rt] && ma[rt] <= b) return sum[rt];

    }

    int m = (l + r) >> 1;

    long long temp = 0;

    if (L <= m)

        temp += get_ans(L, R, l, m, rt << 1);

    if (m < R)

        temp += get_ans(L, R, m + 1, r, rt << 1 | 1);

    return temp;

}

long long calc(int x, int y) {

    long long temp = 0;

    while (uppest[x] != uppest[y]) {

        if (dep[uppest[x]] > dep[uppest[y]]) swap(x, y);

        //dep[x] < dep[y] ok

        temp += get_ans(idx[uppest[y]], idx[y], 1, n, 1);

        y = fat[uppest[y]];

    }

    if (dep[x] > dep[y]) swap(x, y);

    temp += get_ans(idx[x], idx[y], 1, n, 1);

    return temp;

}

void deal() {

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

        int s, t;

        cin >> s >> t >> a >> b;

        cout << calc(s, t);

        if (i == m)

            cout << endl;

        else

            cout << ' ';

    }

}

int main() {

    //freopen("F:\\rush.txt", "r", stdin);

    ios::sync_with_stdio(0), cin.tie(0);

    while (cin >> n >> m) {

        for (int i = 1; i <= n; i++) cin >> c[i];

        for (int i = 1; i <= n; i++) g[i].clear();

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

            int x, y;

            cin >> x >> y;

            g[x].push_back(y), g[y].push_back(x);

        }

        dep[1] = 0;

        dfs1(1, 0);

        cnt = 0;

        dfs2(1, 1);

        pre();

        deal();

    }

    return 0;

}

巴特西

【 2017 Multi-University Training Contest - Team 9 && hdu 6162】Ch’s gift