大家好，欢迎来到IT知识分享网。
定义
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。
树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。
重链剖分可以将树上的任意一条路径划分成不超过\(O(logn)\)条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。
重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。
如：
- 修改 树上两点之间的路径上 所有点的值。
- 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。
除了配合数据结构来维护树上路径信息，树剖还可以用来 \(O(logn)\)（且常数较小）地求 LCA。在某些题目中，还可以利用其性质来灵活地运用树剖。
来自OIWIKI
重链剖分
性质
- 经过一条轻边，子树大小翻倍，所以只会经过\(O(logn)\)条轻边
- 两条路径最后一定会跳到同一条重链上
如此一来，旧可以把树上路径问题转变成\(logn\)个区间问题，用上一些数据结构进行维护。
例题
[ZJOI2008]树的统计
题目描述
一棵树上有 \(n\) 个节点，编号分别为 \(1\) 到 \(n\)，每个节点都有一个权值 \(w\)。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点 \(u\) 的权值改为 \(t\)。
II. QMAX u v: 询问从点 \(u\) 到点 \(v\) 的路径上的节点的最大权值。
III. QSUM u v: 询问从点 \(u\) 到点 \(v\) 的路径上的节点的权值和。
注意：从点 \(u\) 到点 \(v\) 的路径上的节点包括 \(u\) 和 \(v\) 本身。
输入格式
输入文件的第一行为一个整数 \(n\)，表示节点的个数。
接下来 \(n-1\) 行，每行 \(2\) 个整数 \(a\) 和 \(b\)，表示节点 \(a\) 和节点 \(b\) 之间有一条边相连。
接下来一行 \(n\) 个整数，第 \(i\) 个整数 \(w_i\) 表示节点 \(i\) 的权值。
接下来 \(1\) 行，为一个整数 \(q\)，表示操作的总数。
接下来 \(q\) 行，每行一个操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。
输出格式
对于每个 QMAX 或者 QSUM 的操作，每行输出一个整数表示要求输出的结果。
样例输入 #1
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
样例输出 #1
4
1
2
2
10
6
5
6
5
16
提示
对于 \(100 \%\) 的数据，保证 \(1\le n \le 3\times 10^4\)，\(0\le q\le 2\times 10^5\)。
中途操作中保证每个节点的权值 \(w\) 在 \(-3\times 10^4\) 到 \(3\times 10^4\) 之间。
思路
树链剖分以后对整个DFS序建线段树，这样子重链的一段就是连续的一段，可以直接\(O(logn)\)的时间复杂度下解决区间求和和求最大值，轻链部分则一步步挪，由于最多会有\(logn\)的轻链，所以只会移动\(logn\)次。
每次查询的是跳过的点，不包括下次要到达的点。类似于左闭右开区间。
代码实现
const int N = 101000;
int n, m, a[N];
vector<int> e[N];
int l[N], r[N], idx[N];
int sz[N], hs[N], tot, top[N], dep[N], fa[N];
template<class T>void rd(T &x) {
x=0; int f=0; char ch=getchar();
while (ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
struct info {
int maxv, sum;
};
info operator + (const info &l, const info &r) {
return (info){max(l.maxv, r.maxv), l.sum + r.sum};
}
struct node {
info val;
} seg[N * 4];
// [l, r]
void update(int id) {
seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
void build(int id, int l, int r) {
if (l == r) {
seg[id].val = {a[idx[l]], a[idx[l]]};
} else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
}
// 节点为id，对应的区间为[l, r]，修改a[pos] -> val
void change(int id, int l, int r, int pos, int v) {
if (l == r) {
// l -> dfsn-> l
seg[id].val = {v, v};
} else {
int mid = l + r >> 1;
if (pos <= mid) change(id * 2, l, mid, pos, v);
else change(id * 2 + 1, mid + 1, r, pos, v);
// 重要‼️
update(id);
}
}
// [ql, qr]表示查询的区间
info query(int id, int l, int r, int ql, int qr) {
if (l == ql && r == qr) return seg[id].val;
int mid = (l + r) / 2;
// [l, mid] , [mid + 1, r]
if (qr <= mid) return query(id * 2, l, mid, ql, qr);
else if (ql > mid) return query(id * 2 + 1, mid + 1, r, ql,qr);
else {
// qr > mid, ql <= mid
// [ql, mid], [mid + 1, qr]
return query(id * 2, l, mid, ql, mid) +
query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}
}
info query(int u, int v) {
info ans{(int)-1e9, 0};
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
// 维护的是跳过的点的信息，不包括到达的点，所以是top[v]
ans = ans + query(1, 1, n, l[top[v]], l[v]);
v = fa[top[v]];
} else {
ans = ans + query(1, 1, n, l[top[u]], l[u]);
u = fa[top[u]];
}
}
return dep[u] < dep[v] ? ans = ans + query(1,1,n,l[u],l[v]) : ans = ans + query(1,1,n,l[v],l[u]);
}
void dfs_init(int u, int f) {
sz[u] = 1;
hs[u] = -1;
dep[u] = dep[f] + 1;
fa[u] = f;
for (auto v : e[u]) {
if (v == f) continue;
dfs_init(v, u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]])
hs[u] = v;
}
}
// 求出重链链头元素，每个点DFS序
void dfs2(int u, int t) {
l[u] = ++tot;
top[u] = t;
idx[tot] = u;
// 先访问重儿子
if (hs[u] != -1) dfs2(hs[u], t);
for (auto v : e[u])
if (v != fa[u] && v != hs[u])
dfs2(v, v);
r[u] = tot;
}
int main(void) {
//ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
rd(n);
rep(i,1,n-1) {
int u, v;
rd(u), rd(v);
e[u].pb(v), e[v].pb(u);
}
rep(i,1,n) rd(a[i]);
dfs_init(1,0);
dfs2(1,1);
build(1,1,n);
rd(m);
rep(i,1,m) {
static char op[20];
scanf("%s",op);
int u, v;
rd(u), rd(v);
if (op[0] == 'C') change(1, 1, n, l[u], v);
else {
info ans = query(u, v);
if (op[1] == 'M') printf("%d\n",ans.maxv);
else printf("%d\n",ans.sum);
}
}
return 0;
}
SDOI2011,染色
题目描述
给定一棵 \(n\) 个节点的无根树，共有 \(m\) 个操作，操作分为两种：
- 将节点 \(a\) 到节点 \(b\) 的路径上的所有点（包括 \(a\) 和 \(b\)）都染成颜色 \(c\)。
- 询问节点 \(a\) 到节点 \(b\) 的路径上的颜色段数量。
颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 \(n\) 和操作个数 \(m\)。
第二行有 \(n\) 个用空格隔开的整数，第 \(i\) 个整数 \(w_i\) 代表结点 \(i\) 的初始颜色。
第 \(3\) 到第 \((n + 1)\) 行，每行两个用空格隔开的整数 \(u, v\)，代表树上存在一条连结节点 \(u\) 和节点 \(v\) 的边。
第 \((n + 2)\) 到第 \((n + m + 1)\) 行，每行描述一个操作，其格式为：
每行首先有一个字符 \(op\)，代表本次操作的类型。
- 若 \(op\) 为
C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 \(a, b, c\)，代表将 \(a\) 到 \(b\) 的路径上所有点都染成颜色 \(c\)。 - 若 \(op\) 为
Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 \(a, b\)，表示查询 \(a\) 到 \(b\) 路径上的颜色段数量。
样例输入
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
样例输出
3
1
2
思路
树链剖分后，用线段树维护树的路径信息。
整棵树可以剖成若干成—-····—–·—-··——-这样的链状结构
剖分之后，按先重后轻的顺序求出整棵树的DFS序列，可以发现重链的DFS序编号是连续的。
对整个DFS序建线段树，对于每段重链都可以直接变换成DFS序的对应段。
如何找出路径颜色段数
考虑两个区间：左区间123和右区间321，左边段数是3，右边段数也是3，合并后新区间为123321，总段数是5。
可以看到，两端合并的时候，会造成影响的其实是左区间的右端点和右区间的左端点是否一致，如果一致，则答案数目减少一段，不一致则是左右区间段数直接相加。
如何进行段数合并
合并的时候需要分清楚当前跳的是哪一条链，因为路径是呈现人字形的，左边路径跳上来途中无法和右边路径进行归并，所以要分别记录左右两边链的信息。
同一条链进行信息更新的时候，也需要注意方向，因为我们是依照DFS序从上往下建立的线段树，左端点在上右端点在下，但是我们求路径的时候是从下往上求的，就好比左端点在下，右端点在上，所以要颠倒左右端点。
例如：
1. ansv = query(1, 1, n, l[top[v]], l[v]) + ansv;// √
2. ansv = ansv + query(1, 1, n, l[top[v]], l[v]);// ×
多dao’dao几句，此处记一下困扰多时的地方：方向问题，DFS从上到下，类比成数组形式就是1->2->3… 如此扩展下去，左端点是上边深度浅的点，右端点是下边深度大的点，但是我们从下往上做的时候,，左端点就是深度大的点，右端点就是深度浅的点，如此一来区间信息就会对不上号，所以需要交换一下端点值。
代码实现
const int N = 1e5 + 10;
int n, m, tot;
int l[N], r[N], idx[N], sz[N], hs[N], top[N], fa[N], w[N],dep[N];
vector<int> e[N];
struct info {
int lc, rc, sum;
};
info operator + (const info &l, const info &r) {
info res;
res.lc = l.lc, res.rc = r.rc, res.sum = l.sum + r.sum;
if (l.rc == r.lc) {
--res.sum;
}
return res;
}
struct SegmentTree {
#define lson id << 1
#define rson id << 1 | 1
struct Tree {
info val;
int lazy;
} seg[N << 2];
inline void update(int id) {
seg[id].val = seg[lson].val + seg[rson].val;
}
inline void settag(int id, int c) {
seg[id].val = {c, c, 1};
seg[id].lazy = c;
}
inline void pushdown(int id) {
if (seg[id].lazy != 0) {
settag(lson, seg[id].lazy);
settag(rson, seg[id].lazy);
seg[id].lazy = 0;
}
}
inline void bulid(int id, int l, int r) {
seg[id].lazy = 0;
if (l == r) {
seg[id].val = {w[idx[l]], w[idx[l]], 1};
} else {
int mid = l + r >> 1;
bulid(lson, l, mid);
bulid(rson, mid + 1, r);
update(id);
}
}
inline void modify(int id, int l, int r, int ql, int qr, int c) {
if (l == ql && r == qr) {
settag(id, c);
} else {
pushdown(id);
int mid = l + r >> 1;
if (qr <= mid) {
modify(lson, l, mid, ql, qr, c);
} else if (ql > mid) {
modify(rson, mid + 1, r, ql, qr, c);
} else {
modify(lson, l, mid, ql, mid,c);
modify(rson, mid + 1, r, mid + 1, qr, c);
}
update(id);
}
}
inline info query(int id, int l, int r, int ql, int qr) {
if (l == ql && r == qr) {
return seg[id].val;
} else {
pushdown(id);
int mid = l + r >> 1;
if (qr <= mid) {
return query(lson, l, mid, ql, qr);
} else if (ql > mid) {
return query(rson, mid + 1, r, ql, qr);
} else {
return query(lson, l, mid, ql, mid) +
query(rson, mid + 1, r, mid + 1, qr);
}
}
}
} tree;
inline int read() {
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void dfs1(int u, int f) {
sz[u] = 1;
fa[u] = f;
dep[u] = dep[f] + 1;
hs[u] = -1;
for (auto v : e[u]) {
if (v == f) continue;
dfs1(v, u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]]) {
hs[u] = v;
}
}
}
inline void dfs2(int u, int t) {
l[u] = ++tot;
top[u] = t;
idx[tot] = u;
if (hs[u] != -1) dfs2(hs[u], t);
for (auto v : e[u]) {
if (v != fa[u] && v != hs[u]) {
dfs2(v, v);
}
}
r[u] = tot;
}
inline info query(int u, int v) {
info ansl = {0,0,0}, ansr = {0,0,0};
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
ansl = tree.query(1, 1, n, l[top[u]], l[u]) + ansl;
u = fa[top[u]];
} else {
ansr = tree.query(1, 1, n, l[top[v]], l[v]) + ansr;
v = fa[top[v]];
}
}
if (dep[u] > dep[v]) {
ansl = tree.query(1, 1, n, l[v], l[u]) + ansl;
} else {
ansr = tree.query(1, 1, n, l[u], l[v]) + ansr;
}
swap(ansl.lc, ansl.rc);
return ansl + ansr;
}
inline void modify(int u, int v, int c) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
tree.modify(1, 1, n, l[top[u]], l[u], c);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
tree.modify(1, 1, n, l[v], l[u], c);
}
int main(void) {
n = read(), m = read();
rep(i,1,n) w[i] = read();
rep(i,1,n-1) {
int u, v;
u = read(), v = read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
tree.bulid(1, 1, n);
rep(i,1,m) {
static char op[20];
scanf("%s",op);
if (op[0] == 'Q') {
int u, v;
u = read(), v = read();
printf("%d\n",query(u,v).sum);
} else {
int u, v, c;
u = read(), v = read(), c = read();
modify(u, v, c);
}
}
return 0;
}
NOI2015, 软件包管理器
题目背景
Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。
题目描述
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(a\) 依赖软件包 \(b\)，那么安装软件包 \(a\) 以前，必须先安装软件包 \(b\)。同时，如果想要卸载软件包 \(b\)，则必须卸载软件包 \(a\)。
现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 \(m\) 个软件包 \(a_1,a_2, \dots , a_m\)，对于 \(i<m\)，\(a_i\) 依赖 \(a_{i+1}\)，而 \(a_m\) 依赖 \(a_1\) 的情况）。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。
注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。
输入格式
第一行一个正整数 \(n\)，表示软件包个数，从 \(0\) 开始编号。
第二行有 \(n-1\) 个整数，第 \(i\) 个表示 \(i\) 号软件包依赖的软件包编号。
然后一行一个正整数 \(q\)，表示操作个数，格式如下：
install x表示安装 \(x\) 号软件包uninstall x表示卸载 \(x\) 号软件包
一开始所有软件包都是未安装的。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出格式
输出 \(q\) 行，每行一个整数，表示每次询问的答案。
样例输入 #1
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
样例输出 #1
3
1
3
2
3
样例输入 #2
10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9
样例输出 #2
1
3
2
1
3
1
1
1
0
1
思路
树链剖分后，用线段树维护区间1的信息，每次查询其实就是上一次查询-本次查线段树根节点的信息的绝对值。
单条链网上不断修改，比较的好写。
代码实现
const int N = 1e5 + 10;
int n, m, tot;
int l[N], r[N], idx[N], sz[N], hs[N], top[N], fa[N], w[N],dep[N];
vector<int> e[N];
struct SegmentTree {
#define lson id << 1
#define rson id << 1 | 1
struct Tree {
int cnt, sz, lazy;
} seg[N << 2];
inline void update(int id) {
seg[id].cnt = seg[lson].cnt + seg[rson].cnt;
}
inline void settag(int id, int c) {
if (c == 1) {
seg[id].cnt = seg[id].sz;
} else if (c == 0) {
seg[id].cnt = 0;
}
seg[id].lazy = c;
}
inline void pushdown(int id) {
if (seg[id].lazy != -1) {
settag(lson, seg[id].lazy);
settag(rson, seg[id].lazy);
seg[id].lazy = -1;
}
}
inline void bulid(int id, int l, int r) {
seg[id].sz = r - l + 1;
seg[id].lazy = -1;
if (l == r) {
return;
} else {
int mid = l + r >> 1;
bulid(lson, l, mid);
bulid(rson, mid + 1, r);
update(id);
}
}
inline void modify(int id, int l, int r, int ql, int qr, int c) {
if (l == ql && r == qr) {
settag(id, c);
} else {
pushdown(id);
int mid = l + r >> 1;
if (qr <= mid) {
modify(lson, l, mid, ql, qr, c);
} else if (ql > mid) {
modify(rson, mid + 1, r, ql, qr, c);
} else {
modify(lson, l, mid, ql, mid,c);
modify(rson, mid + 1, r, mid + 1, qr, c);
}
update(id);
}
}
} tree;
inline int read() {
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void dfs1(int u, int f) {
sz[u] = 1;
fa[u] = f;
dep[u] = dep[f] + 1;
hs[u] = -1;
for (auto v : e[u]) {
if (v == f) continue;
dfs1(v, u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]]) {
hs[u] = v;
}
}
}
inline void dfs2(int u, int t) {
l[u] = ++tot;
top[u] = t;
idx[tot] = u;
if (hs[u] != -1) dfs2(hs[u], t);
for (auto v : e[u]) {
if (v != fa[u] && v != hs[u]) {
dfs2(v, v);
}
}
r[u] = tot;
}
inline void install(int x) {
while (x != 0) {
tree.modify(1, 1, n, l[top[x]], l[x], 1);
x = fa[top[x]];
}
}
inline void uninstall(int x) {
tree.modify(1, 1, n, l[x], r[x], 0);
}
int main(void) {
n = read();
rep(i,2,n) {
fa[i] = read();
++fa[i];
e[fa[i]].push_back(i);
}
dfs1(1, 0);
dfs2(1, 1);
tree.bulid(1,1,n);
m = read();
int pre = 0;
rep(i,1,m) {
int x;
static char op[10];
scanf("%s%d",op, &x);
x++;
if (op[0] == 'i') {
install(x);
} else {
uninstall(x);
}
printf("%d\n",abs(pre - tree.seg[1].cnt));
pre = tree.seg[1].cnt;
}
return 0;
}
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/30294.html
