你没有看错，这次是一个八题系列:joy:
不含树剖算法详解，供已经会树剖的同学刷题食用
Luogu3384 【模板】树链剖分
树剖的模板题，包含了树剖题基本会涉及到的所有操作。
如果是询问一条链的长度，需要暴跳求和。
其他的信息都用线段树维护即可（区间修改、询问）
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 100000 + 5;
int n, m, r, Mod, num, root;
int head[SIZE], size[SIZE], son[SIZE], fa[SIZE], depth[SIZE], Rank[SIZE], top[SIZE], id[SIZE], a[SIZE];
struct Segment_tree {
int l, r, lson, rson, tag, sum;
} tree[SIZE << 2];
struct node {
int to, Next;
} edge[SIZE << 1];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS1(int u)
{
size[u] = 1, depth[u] = depth[fa[u]] + 1;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u;
DFS1(v);
size[u] += size[v];
if (size[son[u]] < size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
top[u] = TOP, id[u] = ++num, Rank[num] = u;
if (son[u]) DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != fa[u] && v != son[u]) DFS2(v, v);
}
}
inline int pos(int x) { return tree[x].r - tree[x].l + 1; }
inline void Pushup(int x) { tree[x].sum = (tree[tree[x].lson].sum + tree[tree[x].rson].sum) % Mod; }
inline void Pushdown(int x)
{
if (tree[x].tag) {
int lson = tree[x].lson, rson = tree[x].rson, tag = tree[x].tag;
(tree[lson].tag += tag) %= Mod, (tree[rson].tag += tag) %= Mod;
(tree[lson].sum += tag * pos(lson)) %= Mod, (tree[rson].sum += tag * pos(rson)) %= Mod;
tree[x].tag = 0;
}
}
inline void Build(int l, int r, int x)
{
if (l == r) {
tree[x].sum = a[Rank[l]], tree[x].l = tree[x].r = l;
return;
}
tree[x].lson = num++, tree[x].rson = num++;
int Mid = (l + r) >> 1;
Build(l, Mid, tree[x].lson), Build(Mid + 1, r, tree[x].rson);
tree[x].l = tree[tree[x].lson].l, tree[x].r = tree[tree[x].rson].r;
Pushup(x);
}
inline void Change(int l, int r, int val, int x)
{
if (tree[x].l >= l && tree[x].r <= r) {
(tree[x].tag += val) %= Mod, (tree[x].sum += pos(x) * val) %= Mod;
return;
}
Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1;
if (Mid >= l) Change(l, r, val, tree[x].lson);
if (Mid < r) Change(l, r, val, tree[x].rson);
Pushup(x);
}
inline int Query(int l, int r, int x)
{
if (tree[x].l >= l && tree[x].r <= r)
return tree[x].sum;
Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1, ans = 0;
if (Mid >= l) ans += Query(l, r, tree[x].lson);
if (Mid < r) ans += Query(l, r, tree[x].rson);
return ans % Mod;
}
inline int Get_sum(int u, int v)
{
int ret = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
(ret += Query(id[top[u]], id[u], root)) %= Mod;
u = fa[top[u]];
}
if (id[u] > id[v]) std::swap(u, v);
return (ret + Query(id[u], id[v], root)) % Mod;
}
inline void Update(int u, int v, int val)
{
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
Change(id[top[u]], id[u], val, root);
u = fa[top[u]];
}
if (id[u] > id[v]) std::swap(u, v);
Change(id[u], id[v], val, root);
}
signed main()
{
int u, v;
n = read(), m = read(), r = read(), Mod = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i < n; i++) {
u = read(), v = read();
Addedge(u, v);
Addedge(v, u);
}
num = 0;
DFS1(r); DFS2(r, r);
num = 0;
Build(1, n, root = num++);
int opt, x, y, k;
while (m--) {
opt = read();
if (opt == 1) {
x = read(), y = read(), k = read();
Update(x, y, k);
}
if (opt == 2) {
x = read(), y = read();
printf("%lld\n", Get_sum(x, y));
}
if (opt == 3) {
x = read(), y = read();
Change(id[x], id[x] + size[x] - 1, y, root);
}
if (opt == 4) {
x = read();
printf("%lld\n", Query(id[x], id[x] + size[x] - 1, root));
}
}
return 0;
}
Luogu2146 [NOI2015]软件包管理器
树剖模板题，看清楚题意就会做。
按照依赖关系建树以后，它的删除操作就是把它的子树全部清零，安装软件就是该节点到根节点的路径变为1
回答的时候先记住修改前线段树root的值，在与修改后的作差即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100000 + 5;
int n, Q, num;
int head[SIZE], son[SIZE], fa[SIZE], depth[SIZE], id[SIZE], top[SIZE], size[SIZE];
struct node {
int to, Next;
} edge[SIZE << 1];
struct Segment_tree {
int sum, tag, l, r, lson, rson;
} tree[SIZE << 2];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS1(int u)
{
size[u] = 1, depth[u] = depth[fa[u]] + 1;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u;
DFS1(v);
size[u] += size[v];
if (size[son[u]] < size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
id[u] = ++num, top[u] = TOP;
if (!son[u]) return;
DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u]) DFS2(v, v);
}
}
inline void Build(int x, int l, int r)
{
tree[x].l = l, tree[x].r = r, tree[x].sum = 0, tree[x].tag = -1;
if (l == r) return;
int mid = (l + r) >> 1;
Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
return;
}
inline void Pushdown(int x)
{
tree[x << 1].sum = (tree[x << 1].r - tree[x << 1].l + 1) * tree[x].tag;
tree[x << 1 | 1].sum = (tree[x << 1 | 1].r - tree[x << 1 | 1].l + 1) * tree[x].tag;
tree[x << 1].tag = tree[x << 1| 1].tag = tree[x].tag;
tree[x].tag = -1;
}
inline int Query(int x,int l,int r)
{
if (tree[x].r <= r && tree[x].l >= l) return tree[x].sum;
if (tree[x].tag != -1) Pushdown(x);
return Query(x << 1, l, r) + Query(x << 1 | 1, l, r);
}
inline void Change(int x,int l,int r,int val)
{
if (tree[x].r < l || tree[x].l > r) return;
if (tree[x].r <= r && tree[x].l >= l) {
tree[x].sum = (tree[x].r - tree[x].l + 1) * val;
tree[x].tag = val;
return;
}
if(tree[x].tag != -1) Pushdown(x);
Change(x << 1, l, r, val); Change(x << 1 | 1, l, r, val);
tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
return;
}
inline void Update(int u, int v, int val)
{
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]]) std::swap(u,v);
Change(1, id[top[u]], id[u], val);
u = fa[top[u]];
}
if (depth[u] > depth[v]) std::swap(u,v);
Change(1, id[u], id[v], val);
return;
}
int main()
{
n = read();
for (int i = 2; i <= n; i++) {
int u = read() + 1;
Addedge(u, i);
}
num = 0; DFS1(1);
num = 0; DFS2(1, 1);
Build(1, 1, num);
Q = read();
string opt;
while (Q--) {
std::cin >> opt;
int tmp1 = tree[1].sum;
if (opt == "install") {
int x = read() + 1;
Update(1,x,1);
int tmp2 = tree[1].sum;
printf("%d\n", abs(tmp1 - tmp2));
}
if (opt == "uninstall") {
int x = read() + 1;
Change(1,id[x],id[x]+size[x]-1,0);
int tmp2 = tree[1].sum;
printf("%d\n", abs(tmp1 - tmp2));
}
}
return 0;
}
Luogu2590 [ZJOI2008]树的统计
比较简单的一道树剖，线段树部分更加简单，能单点修改区间查询即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 30000 + 5;
int n, Q, num, cnt;
int head[SIZE], son[SIZE], Size[SIZE], top[SIZE], depth[SIZE], fa[SIZE], id[SIZE], Rank[SIZE], w[SIZE];
struct node {
int to, Next;
} edge[SIZE << 1];
struct Segment_tree {
int sum, Max;
} tree[SIZE << 2];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS1(int u)
{
depth[u] = depth[fa[u]] + 1, Size[u] = 1;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u;
DFS1(v);
Size[u] += Size[v];
if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
if (!son[u]) return;
DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u]) DFS2(v, v);
}
}
inline void Pushup(int x)
{
tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
tree[x].Max = std::max(tree[x << 1].Max, tree[x << 1 | 1].Max);
}
inline void Build(int l, int r, int x)
{
if (l == r) {
tree[x].sum = tree[x].Max = w[Rank[l]];
return;
}
int Mid = (l + r) >> 1;
Build(l, Mid, x << 1); Build(Mid + 1, r, x << 1 | 1);
Pushup(x);
}
inline void Change(int x, int p, int l, int r, int val)
{
if (l == r) {
tree[x].sum = tree[x].Max = val;
return;
}
int Mid = (l + r) >> 1;
if (p <= Mid) Change(x << 1, p, l, Mid, val);
else Change(x << 1 | 1, p, Mid + 1, r, val);
Pushup(x);
}
inline int Query_sum(int x, int L, int R, int l, int r)
{
if (L <= l && r <= R) return tree[x].sum;
int Mid = (l + r) >> 1, sum = 0;
if (L <= Mid) sum += Query_sum(x << 1, L, R, l, Mid);
if (R > Mid) sum += Query_sum(x << 1 | 1, L, R, Mid + 1, r);
return sum;
}
inline int Query_max(int x, int L, int R, int l, int r)
{
if (L <= l && r <= R) return tree[x].Max;
int Mid = (l + r) >> 1, sum = -2e9;
if (L <= Mid) sum = std::max(sum, Query_max(x << 1, L, R, l, Mid));
if (R > Mid) sum = std::max(sum, Query_max(x << 1 | 1, L, R, Mid + 1, r));
return sum;
}
inline int Get_max(int u, int v)
{
int ans = -2e9;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans = std::max(ans, Query_max(1, id[top[u]], id[u], 1, n));
u = fa[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
ans = std::max(ans, Query_max(1, id[u], id[v], 1, n));
return ans;
}
inline int Get_sum(int u, int v)
{
int ans = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans += Query_sum(1, id[top[u]], id[u], 1, n);
u = fa[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
ans += Query_sum(1, id[u], id[v], 1, n);
return ans;
}
int main()
{
// freopen("data.in", "r", stdin));
int u, v, t;
n = read();
for (int i = 1; i < n; i++) {
u = read(), v = read();
Addedge(u, v); Addedge(v, u);
}
for (int i = 1; i <= n; i++) w[i] = read();
cnt = 0; DFS1(1);
cnt = 0; DFS2(1, 1);
Build(1, n, 1);
Q = read();
string opt;
while (Q--) {
std::cin >> opt;
if (opt == "CHANGE") {
u = read(), t = read();
Change(1, id[u], 1, n, t);
}
if (opt == "QMAX") {
u = read(), v = read();
printf("%d\n", Get_max(u, v));
}
if (opt == "QSUM") {
u = read(), v = read();
printf("%d\n", Get_sum(u, v));
}
}
return 0;
}
Luogu3178 [HAOI2015]树上操作
"您好这一题跟上一题有差别吗？"
"您好没有"
:joy:
其实是有的，线段树部分仍然只需单点修改区间查询即可。
这个修改是修改子树中所有点的点权，其他的修改也相应地变为增加而不是直接改变。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 100000 + 5;
int n, m, num, cnt;
int head[SIZE], a[SIZE], son[SIZE], Size[SIZE], fa[SIZE], depth[SIZE], id[SIZE], Rank[SIZE], top[SIZE];
struct node {
int to, Next;
} edge[SIZE << 1];
struct Segment_tree {
int l, r, sum, tag;
} tree[SIZE << 2];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS1(int u)
{
depth[u] = depth[fa[u]] + 1, Size[u] = 1;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u;
DFS1(v);
Size[u] += Size[v];
if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
if (!son[u]) return;
DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u]) DFS2(v, v);
}
}
inline int pos(int x) { return tree[x].r - tree[x].l + 1; }
inline void Pushdown(int x)
{
if (tree[x].tag) {
tree[x << 1].sum += pos(x << 1) * tree[x].tag;
tree[x << 1 | 1].sum += pos(x << 1 | 1) * tree[x].tag;
tree[x << 1].tag += tree[x].tag, tree[x << 1 | 1].tag += tree[x].tag;
tree[x].tag = 0;
}
}
inline void Build(int x, int l, int r)
{
tree[x].l = l, tree[x].r = r;
if (l == r) {
tree[x].sum = a[Rank[l]];
return;
}
int Mid = (l + r) >> 1;
Build(x << 1, l, Mid); Build(x << 1 | 1, Mid + 1, r);
tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
}
inline void Change(int x, int l, int r, int val)
{
if (l <= tree[x].l && tree[x].r <= r) {
tree[x].sum += val * pos(x), tree[x].tag += val;
return;
}
Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1;
if (l <= Mid) Change(x << 1, l, r, val);
if (r > Mid) Change(x << 1 | 1, l, r, val);
tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
}
inline int Query(int x, int l, int r)
{
if (l <= tree[x].l && tree[x].r <= r) return tree[x].sum;
Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1, sum = 0;
if (l <= Mid) sum += Query(x << 1, l, r);
if (r > Mid) sum += Query(x << 1 | 1, l, r);
return sum;
}
inline int Get_ans(int u, int v)
{
int ans = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans += Query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
ans += Query(1, id[u], id[v]);
return ans;
}
signed main()
{
int u, v;
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i < n; i++) {
u = read(), v = read();
Addedge(u, v);
Addedge(v, u);
}
cnt = 0; DFS1(1);
cnt = 0; DFS2(1, 1);
cnt = 0; Build(1, 1, n);
while (m--) {
int opt = read();
if (opt == 1) {
int x = read(), val = read();
Change(1, id[x], id[x], val);
}
if (opt == 2) {
u = read(), v = read();
Change(1, id[u], id[u] + Size[u] - 1, v);
}
if (opt == 3) {
u = read();
printf("%lld\n", Get_ans(1, u));
}
}
return 0;
}
Luogu1505 [国家集训队]旅游
这个题是最傻逼的一个，操作贼多，代码超长
线段树维护单点修改，区间修改（乘），区间询问最大最小值，求和。
并且还是询问一条链的以上信息。
看代码好了。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 20000 + 5;
int n, Q, num, cnt;
int head[SIZE], w[SIZE], son[SIZE], Size[SIZE], depth[SIZE], fa[SIZE], id[SIZE], Rank[SIZE], top[SIZE];
struct node {
int to, v, Next;
} edge[SIZE << 2];
struct Segment_tree {
int l, r, tag, sum, Min, Max;
} tree[SIZE << 2];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y, int z)
{
edge[++num].to = y;
edge[num].v = z;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS1(int u)
{
Size[u] = 1;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u, w[v] = edge[i].v, depth[v] = depth[u] + 1;
DFS1(v);
Size[u] += Size[v];
if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
if (son[u]) DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != fa[u] && v != son[u]) DFS2(v, v);
}
}
inline void Pushdown(int x)
{
tree[x << 1].tag += tree[x].tag, tree[x << 1].tag %= 2;
tree[x << 1 | 1].tag += tree[x]. tag, tree[x << 1 | 1].tag %= 2;
tree[x << 1].sum *= -1, tree[x << 1 | 1].sum *= -1;
std::swap(tree[x << 1].Max, tree[x << 1].Min);
tree[x << 1].Max *= -1, tree[x << 1].Min *= -1;
std::swap(tree[x << 1 | 1].Max, tree[x << 1 | 1].Min);
tree[x << 1 | 1].Max *= -1, tree[x << 1 | 1].Min *= -1;
tree[x].tag = 0;
}
inline void Pushup(int x)
{
tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
tree[x].Max = std::max(tree[x << 1].Max, tree[x << 1 | 1].Max);
tree[x].Min = std::min(tree[x << 1].Min, tree[x << 1 | 1].Min);
}
inline void Build(int x, int l, int r)
{
tree[x].l = l, tree[x].r = r, tree[x].tag = 0;
if (l == r) {
tree[x].sum = tree[x].Max = tree[x].Min = w[Rank[l]];
return;
}
int Mid = (l + r) >> 1;
Build(x << 1, l, Mid); Build(x << 1 | 1, Mid + 1, r);
Pushup(x);
}
inline void changeSingle(int x, int p, int val)
{
if (tree[x].l == tree[x].r) {
tree[x].sum = tree[x].Min = tree[x].Max = val;
return;
}
if (tree[x].tag) Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1;
if (Mid >= p) changeSingle(x << 1, p, val);
else changeSingle(x << 1 | 1, p, val);
Pushup(x);
}
inline void changeInterval(int x, int l, int r)
{
if (l <= tree[x].l && tree[x].r <= r) {
tree[x].tag++; tree[x].tag %= 2; tree[x].sum *= -1;
std::swap(tree[x].Max, tree[x].Min);
tree[x].Max *= -1, tree[x].Min *= -1;
return;
}
if (tree[x].tag) Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1;
if (Mid >= l) changeInterval(x << 1, l, r);
if (Mid + 1 <= r) changeInterval(x << 1 | 1, l, r);
Pushup(x);
}
inline int querySum(int x, int l, int r)
{
if (l <= tree[x].l && tree[x].r <= r) return tree[x].sum;
if (tree[x].tag) Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1, sum = 0;
if (l <= Mid) sum += querySum(x << 1, l, r);
if (Mid + 1 <= r) sum += querySum(x << 1 | 1, l, r);
Pushup(x);
return sum;
}
inline int queryMin(int x, int l, int r)
{
if (l <= tree[x].l && tree[x].r <= r) return tree[x].Min;
if (tree[x].tag) Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1, sum = 2e9;
if (l <= Mid) sum = std::min(sum, queryMin(x << 1, l, r));
if (Mid + 1 <= r) sum = std::min(sum, queryMin(x << 1 | 1, l, r));
Pushup(x);
return sum;
}
inline int queryMax(int x, int l, int r)
{
if (l <= tree[x].l && tree[x].r <= r) return tree[x].Max;
if (tree[x].tag) Pushdown(x);
int Mid = (tree[x].l + tree[x].r) >> 1, sum = -2e9;
if (l <= Mid) sum = std::max(sum, queryMax(x << 1, l, r));
if (Mid + 1 <= r) sum = std::max(sum, queryMax(x << 1 | 1, l, r));
Pushup(x);
return sum;
}
inline int getSum(int u, int v)
{
int ans = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans += querySum(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (u == v) return ans;
if (id[u] > id[v]) std::swap(u, v);
ans += querySum(1, id[u] + 1, id[v]);
return ans;
}
inline int getMax(int u, int v)
{
int ans = -2e9;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans = std::max(ans, queryMax(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if (u == v) return ans;
if (id[u] > id[v]) std::swap(u, v);
ans = std::max(ans, queryMax(1, id[u] + 1, id[v]));
return ans;
}
inline int getMin(int u, int v)
{
int ans = 2e9;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans = std::min(ans, queryMin(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if (u == v) return ans;
if (id[u] > id[v]) std::swap(u, v);
ans = std::min(ans, queryMin(1, id[u] + 1, id[v]));
return ans;
}
inline void Update(int u, int v)
{
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
changeInterval(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (u == v) return;
if (id[u] > id[v]) std::swap(u, v);
changeInterval(1, id[u] + 1, id[v]);
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int u, v, d;
n = read();
for (int i = 1; i < n; i++) {
u = read() + 1, v = read() + 1, d = read();
Addedge(u, v, d); Addedge(v, u, d);
}
cnt = 0; DFS1(1);
cnt = 0; DFS2(1, 1);
cnt = 0; Build(1, 1, n);
Q = read();
string opt;
while (Q--) {
std::cin >> opt;
if (opt == "C") {
u = read() + 1, v = read();
changeSingle(1, id[u], v);
}
if (opt == "N") {
u = read() + 1, v = read() + 1;
Update(u, v);
}
if (opt == "SUM") {
u = read() + 1, v = read() + 1;
printf("%d\n", getSum(u, v));
}
if (opt == "MAX") {
u = read() + 1, v = read() + 1;
printf("%d\n", getMax(u, v));
}
if (opt == "MIN") {
u = read() + 1, v = read() + 1;
printf("%d\n", getMin(u, v));
}
}
return 0;
}
Luogu4427 [BJOI2018]求和
这题不是很常规的树剖（就是没有那么多恶心的操作），该题不涉及修改。
观察 k 的范围很小，可以直接在树剖预处理的时候处理出每一个点的 k 次幂，询问倍增暴跳求和即可。
统计答案记得差分。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 300000 + 5;
const int Mod = 998244353;
int n, Q, num;
int head[SIZE], depth[SIZE], size[SIZE], son[SIZE], fa[SIZE], top[SIZE], sum[SIZE][55];
struct node {
int to, Next;
} edge[SIZE << 1];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline int Qpow(int x, int y)
{
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % Mod;
x = x * x % Mod;
y >>= 1;
}
return ans % Mod;
}
inline void DFS1(int u, int father)
{
size[u] = 1;
for (int i = 1; i <= 51; i++) sum[u][i] = (sum[father][i] + Qpow(depth[u], i)); // TEST1
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v == fa[u]) continue;
fa[v] = u, depth[v] = depth[u] + 1;
DFS1(v, u);
size[u] += size[v];
if (size[son[u]] < size[v]) son[u] = v;
}
}
inline void DFS2(int u, int TOP)
{
top[u] = TOP;
if (son[u]) DFS2(son[u], TOP);
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != fa[u] && v != son[u])
DFS2(v, v);
}
}
inline int LCA(int u, int v)
{
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) u = fa[top[u]];
else v = fa[top[v]];
}
if (depth[u] < depth[v]) return u;
return v;
}
signed main()
{
int u, v, k;
n = read();
for (int i = 1; i < n; i++) {
u = read(), v = read();
Addedge(u, v); Addedge(v, u);
}
DFS1(1, 0); DFS2(1, 1);
Q = read();
while (Q--) {
u = read(), v = read(), k = read();
int lca = LCA(u, v);
printf("%lld\n", (sum[u][k] + sum[v][k] - sum[lca][k] - sum[fa[lca]][k]) % Mod);
}
return 0;
}
SP3978 DISQUERY - Distance Query
我是绝对不会告诉你这是倍增LCA题的
其实可以用树剖做的，懒得写了，倍增也能过，码量少，何乐而不为？
跳的时候同时处理 Min[][], Max[][]两个数组就好了。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100000 + 5;
int n, Q, num, t;
int head[SIZE], depth[SIZE], dis[SIZE], f[SIZE][21], Min[SIZE][21], Max[SIZE][21];
struct node {
int to, v, Next;
} edge[SIZE << 1];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y, int z)
{
edge[++num].to = y;
edge[num].v = z;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int u, int fa)
{
f[u][0] = fa;
for (int i = head[u]; i; i = edge[i].Next) {
int v = edge[i].to;
if (v != fa) {
Min[v][0] = Max[v][0] = edge[i].v;
depth[v] = depth[u] + 1;
DFS(v, u);
}
}
}
inline void init()
{
for (int k = 1; k <= 20; k++)
for (int i = 1; i <= n; i++) {
if (f[f[i][k - 1]][k - 1] && f[i][k - 1]) {
f[i][k] = f[f[i][k - 1]][k - 1];
Min[i][k] = std::min(Min[i][k - 1], Min[f[i][k - 1]][k - 1]);
Max[i][k] = std::max(Max[i][k - 1], Max[f[i][k - 1]][k - 1]);
}
}
}
inline void LCA(int u, int v)
{
int ans_min = 2e9, ans_max = -2e9;
if (depth[u] > depth[v]) std::swap(u, v);
for (int i = 20; i >= 0; i--) {
if (depth[u] <= depth[f[v][i]]) {
ans_min = std::min(ans_min, Min[v][i]), ans_max = std::max(ans_max, Max[v][i]);
v = f[v][i];
}
}
if (u == v) {
printf("%d %d\n", ans_min, ans_max);
return;
}
for (int i = 20; i >= 0; i--) {
if (f[u][i] != f[v][i]) {
ans_min = std::min(ans_min, std::min(Min[u][i], Min[v][i])), ans_max = std::max(ans_max, std::max(Max[u][i], Max[v][i]));
u = f[u][i], v = f[v][i];
}
}
ans_min = std::min(ans_min, std::min(Min[u][0], Min[v][0]));
ans_max = std::max(ans_max, std::max(Max[u][0], Max[v][0]));
printf("%d %d\n", ans_min, ans_max);
}
int main()
{
int u, v, d;
n = read();
for (int i = 1; i < n; i++) {
u = read(), v = read(), d = read();
Addedge(u, v, d);
Addedge(v, u, d);
}
depth[1] = 1;
DFS(1, 0);
Min[1][0] = 2e9;
init();
Q = read();
while (Q--) {
u = read(), v = read();
LCA(u, v);
}
return 0;
}
细心的观众可能意识到了到这里其实还只有七题
但是由于 【数据删除】【数据删除】 第八题暂时咕咕咕。
我还是绝对不会告诉你开始标题是树剖九题的
Comments | NOTHING