[JLOI2014]松鼠的新家 (树剖)

题目

P3258 [JLOI2014]松鼠的新家

解析

非常裸的一道树剖题

链上修改+单点查询的板子

记录一下所经过的点\(now[i]\)，每次更新\(now[i-1]到now[i]\)

我们链上更新时上一次到的终点，是这一次一次更新的起点，又因为在\(a_n\)处可以不放糖，所以我们每次链上更新完成后，在上条链的终点位置处糖数\(-1\)。

然后套板子直接做

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int n, m, num, cnt;

int head[N], size[N], f[N], top[N], son[N], dep[N], now[N], id[N];

class node {

    public :

	    int v, nx;

} e[N];

class tree {

	public :

	    int sum, lazy;

	    int len;

} t[N];

#define lson rt << 1

#define rson rt << 1 | 1

template<class T>inline void read(T &x) {

    x = 0; int f = 0; char ch = getchar();

    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

    x = f ? -x : x;

    return ;

}

inline void add(int u, int v) {

    e[++num].nx = head[u], e[num].v = v, head[u] = num;

}

void dfs1(int u, int fa) {

    size[u] = 1;

    for (int i = head[u]; ~i; i = e[i].nx) {

        int v = e[i].v;

        if (v != fa) {

            dep[v] = dep[u] + 1;

            f[v] = u;

            dfs1(v, u);

            size[u] += size[v];

            if (size[v] > size[son[u]]) son[u] = v;

        }

    }

}

void dfs2(int u, int t) {

    id[u] = ++cnt;

    top[u] = t;

    if (son[u]) dfs2(son[u], t);

    for (int i = head[u]; ~i; i = e[i].nx) {

        int v = e[i].v;

        if (v != f[u] && v != son[u]) dfs2(v, v);           //WRONG

    }

}

inline void pushup(int rt) {

    t[rt].sum = t[lson].sum + t[rson].sum;

}

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

    t[rt].len = r - l + 1;

    if (l == r) return;

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

    build(l, m, lson);

    build(m + 1, r, rson);

}

inline void pushdown(int rt) {

    if (t[rt].lazy) {

        t[lson].lazy += t[rt].lazy;

        t[rson].lazy += t[rt].lazy;

        t[lson].sum += t[rt].lazy * t[lson].len;

        t[rson].sum += t[rt].lazy * t[rson].len;

        t[rt].lazy = 0;

    }

}

void update(int L, int R, int c, int l, int r, int rt) {

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

        t[rt].sum += (t[rt].len * c);

        t[rt].lazy += c;

        return;

    }

    pushdown(rt);

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

    if (L <= m) update(L, R, c, l, m, lson);

    if (R > m) update(L, R, c, m + 1, r, rson);

    pushup(rt);

}

int query(int L, int R, int l, int r, int rt) {

    if (L <= l && r <= R) return t[rt].sum;

    pushdown(rt);

    int m = (l + r) >> 1, ans = 0;

    if (L <= m) ans += query(L, R, l, m, lson);

    if (R > m) ans += query(L, R, m + 1, r, rson);

    return ans;

}

void update_chain(int x, int y, int z) {

    int fx = top[x], fy = top[y];

    while (fx != fy) {

        if (dep[fx] < dep[fy]) swap(fx, fy), swap(x, y);

        update(id[fx], id[x], z, 1, cnt, 1);

        x = f[fx], fx = top[x];

    }

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

    update(id[x], id[y], z, 1, cnt, 1);

}

int main() {

    memset(head, -1, sizeof(head));

    read(n);

    for (int i = 1, x; i <= n; ++i) read(x), now[i] = x;

    for (int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);

    f[1] = 0, dep[1] = 0;

    dfs1(1, 0);

    dfs2(1, 1);

    build(1, n, 1);

    for (int i = 2; i <= n; ++i) update_chain(now[i - 1], now[i], 1), update_chain(now[i], now[i], -1);

    for (int i = 1; i <= n; ++i) printf("%d\n", query(id[i], id[i], 1, n, 1));

    return 0;

}

巴特西

[JLOI2014]松鼠的新家 (树剖)

题目

解析

代码

最新文章

热门文章