欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-09 17:37:15
题目 "P3258 [JLOI2014]松鼠的新家" 解析 非常裸的一道树剖题 链上修改+单点查询的板子 记录一下所经过的点$now[i]$,每次更新$now[i 1]到now[i]$ 我们链上更新时上一次到的终点,是这一次一次更新的起点,又因为在$a_n$处可以不放糖,所以我们每次链上更新完成后, ......

题目

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;
}