社区讨论
当我试图这么写树剖(怎么才能这样调用啊TAT)
灌水区参与者 5已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @lo8qcp4s
- 此快照首次捕获于
- 2023/10/27 22:50 2 年前
- 此快照最后确认于
- 2023/10/27 22:50 2 年前
这样写他会报这样一个错[Error] invalid use of non-static data member 'TreeChainSegmentation::inv'
CPP#include<bits/stdc++.h>
#define slen(x) (r[x] - l[x] + 1)
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
int inpt()
{
int x = 0, f = 1;
char ch;
for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-'){
f = -1;
ch = getchar();
}
do{
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return x * f;
}
int n, m, rt, MOD;
int w[MAXN];
struct TreeChainSegmentation {
int hd[MAXN], to[MAXM], nxt[MAXM], tot = 0;
void Add(int x, int y) {
nxt[++tot] = hd[x];
hd[x] = tot;
to[tot] = y;
}
int siz[MAXN], dpt[MAXN], son[MAXN];
int fa[MAXN];
void dfs1(int x, int fath) {
siz[x] = 1;
dpt[x] = dpt[fath] + 1;
fa[x] = fath;
for(int i = hd[x]; i; i = nxt[i]) {
int y = to[i];
if(y == fath) continue;
dfs1(y, x);
siz[x] += siz[y];
}
if(siz[x] > siz[son[fath]]) {
son[fath] = x;
}
}
//------------------------------------------------------------------------------------------------------就是这一坨
int seg[MAXN], top[MAXN], inv[MAXN];
int id = 0;
void dfs2(int x, int tp) {
seg[x] = ++id;
inv[id] = x;
top[x] = tp;
if(!son[x]) return ;
dfs2(son[x], tp);
for(int i = hd[x]; i; i = nxt[i]) {
int y = to[i];
if(y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
struct SegmentTree {
int l[MAXN << 2], r[MAXN << 2];
int tag[MAXN << 2];
int sum[MAXN << 2];
void Build(int x, int L, int R) {
l[x] = L, r[x] = R;
if(L == R) {
sum[x] = w[inv[L]];
return ;
}
int mid = (L + R) >> 1;
Build(x << 1, L, mid);
Build(x << 1 | 1, mid + 1, R);
sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % MOD;
}
//---------------------------------------------------------------------------------------------------------------------------
void PushDown(int x) {
if(tag[x]) {
sum[x << 1] = (sum[x << 1] + 1ll * tag[x] * slen(x << 1) % MOD) % MOD;
tag[x << 1] = (tag[x << 1] + tag[x]) % MOD;
sum[x << 1 | 1] = (sum[x << 1 | 1] + 1ll * tag[x] * slen(x << 1 | 1) % MOD) % MOD;
tag[x << 1 | 1] = (tag[x << 1 | 1] + tag[x]) % MOD;
tag[x] = 0;
}
}
void Change(int x, int L, int R, int v) {
if(L <= l[x] && r[x] <= R) {
tag[x] = (tag[x] + v) % MOD;
sum[x] = (sum[x] + 1ll * v * slen(x) % MOD) % MOD;
return ;
}
PushDown(x);
int mid = (l[x] + r[x]) >> 1;
if(L <= mid) {
Change(x << 1, L, R, v);
}
if(R > mid) {
Change(x << 1 | 1, L, R, v);
}
sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % MOD;
}
int Ask(int x, int L, int R) {
if(L <= l[x] && r[x] <= R) {
return sum[x];
}
PushDown(x);
int mid = (l[x] + r[x]) >> 1;
int val = 0;
if(L <= mid) {
val = (val + Ask(x << 1, L, R)) % MOD;
}
if(R > mid) {
val = (val + Ask(x << 1 | 1, L, R)) % MOD;
}
return val;
}
}str;
void ChangeRoute(int x, int y, int v) {
while(top[x] != top[y]) {
if(dpt[top[x]] < dpt[top[y]]) {
swap(x, y);
}
str.Change(1, seg[top[x]], seg[x], v);
x = fa[top[x]];
}
if(dpt[x] < dpt[y]) {
swap(x, y);
}
str.Change(1, seg[y], seg[x], v);
}
int AskRoute(int x, int y) {
int val = 0;
while(top[x] != top[y]) {
if(dpt[top[x]] < dpt[top[y]]) {
swap(x, y);
}
val = (val + str.Ask(1, seg[top[x]], seg[x])) % MOD;
x = fa[top[x]];
}
if(dpt[x] < dpt[y]) {
swap(x, y);
}
val = (val + str.Ask(1, seg[y], seg[x])) % MOD;
return val;
}
void ChangeSubtree(int x, int v) {
str.Change(1, seg[x], seg[x] + siz[x] - 1, v);
}
int AskSubtree(int x) {
return str.Ask(1, seg[x], seg[x] + siz[x] - 1);
}
}tr;
int main()
{
n = inpt();
m = inpt();
rt = inpt();
MOD = inpt();
for(int i = 1; i <= n; i++) {
w[i] = inpt() % MOD;
}
for(int i = 1; i < n; i++) {
int x = inpt(), y = inpt();
tr.Add(x, y);
tr.Add(y, x);
}
tr.dfs1(rt, 0);
tr.dfs2(rt, rt);
tr.str.Build(1, 1, n);
while(m--) {
int op = inpt();
if(op == 1) {
int x = inpt(), y = inpt(), z = inpt();
tr.ChangeRoute(x, y, z);
continue;
}
if(op == 2) {
int x = inpt(), y = inpt();
printf("%d\n", tr.AskRoute(x, y));
continue;
}
if(op == 3) {
int x = inpt(), z = inpt();
tr.ChangeSubtree(x, z);
continue;
}
if(op = 4) {
int x = inpt();
printf("%d\n", tr.AskSubtree(x));
}
}
return 0;
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...