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