先不考虑-1的d次,维护的信息变换一下变成
= x + k(du - dv)
= x - k*dv + k * du
查询时是单点查询，想到dfn序建立两个树状数组分别维护 x - k*dv 和 k
-1的d次如何判断，可以发现只有当父亲和子节点的深度为一奇一偶时才有-1,其余都是1
那可以在添加时乘(-1)^父亲的深度，再查询时在乘(-1)^查询节点的深度即可
重置，就用set存下操作序列，二分找到符合条件的再删去，由于每个操作最多进set一次出set一次，复杂度不变
最开始读假，以为对包括它为子树的情况也要清除影响，如果这样只能用线段树的区间重重，懒标记增加一个清零，对于操作3强制清零其子树对应的dfn区间即可
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int head[N], nx[N*2], to[N*2], dep[N], in[N], out[N];
int id = 1;
int dfn = 1;
const int inf = 1e9;
void ad(int x, int y) {
to[id] = y;
nx[id] = head[x];
head[x] = id++;
}
void dfs(int cur, int fa) {
dep[cur] = dep[fa] + 1;
in[cur] = dfn++;
for (int i = head[cur]; i > 0; i = nx[i]) {
if (to[i] == fa) {
continue;
}
dfs(to[i], cur);
}
out[cur] = dfn;
}
struct BIT {
int n;
vector<int> a;
BIT(int _n) {
n = _n;
a.assign(n+1,0);
}
void update(int p, int v) {
for (int i = p; i <= n; i += i & -i) {
a[i] = (a[i] + v) % mod;
}
}
void update(int l, int r, int v) {
update(l,v);
update(r+1, -v);
}
int query(int p) {
int sum = 0;
for (int i = p; i > 0; i -= i & -i) {
sum = (sum + a[i]) % mod;
}
return sum;
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
ad(i,x);
ad(x,i);
}
dep[0] = 0;
dfs(1,0);
// (x + k * d)
// x + k * (du - dv)
// x + k * du - k * dv
// x - k * dv + k * du
// 用两个树状数组维护 两个信息
// 有没有 -1 分别用再添加和查询时*深度决定
BIT tree1(n+1), tree2(n+1);
struct node {
int v, x, k;
bool operator< (const node& b) const {
if (in[v] == in[b.v]) {
return x < b.x;
} else {
return in[v] < in[b.v];
}
}
};
set<node> st;
while (q--) {
int op, v, x, k;
cin >> op;
if (op == 1) {
cin >> v >> x >> k;
st.insert({v,x,k});
tree1.update(in[v], out[v] - 1, (x - k * dep[v]) * (dep[v]%2 ? -1 : 1));
tree2.update(in[v], out[v] - 1, k * (dep[v]%2 ? -1 : 1));
} else if (op == 2) {
cin >> v;
int res = tree1.query(in[v]) + tree2.query(in[v]) * (dep[v]);
res = (res*(dep[v]%2 ? -1: 1) + mod) % mod;
cout << res << '\n';
} else if (op == 3) {
cin >> v;
while (true) {
auto fd = st.lower_bound({v,-inf,-inf});
if (fd == st.end() || in[(*fd).v] >= out[v]) {
break;
}
int tv = (*fd).v;
int tx = -(*fd).x, tk = -(*fd).k;
tree1.update(in[tv], out[tv] - 1, (tx - tk * dep[tv]) * (dep[tv]%2 ? -1 : 1));
tree2.update(in[tv], out[tv] - 1, tk * (dep[tv]%2 ? -1 : 1));
st.erase(fd);
}
}
}
return 0;
}