提交时间:2024-07-30 15:54:54

运行 ID: 30812

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9, Mod = 1e9 + 7; vector<int> G[N]; vector<pair<int, int> > opr[N]; set<int> st; int n, m, fa[N], dep[N], dfn[N], to[N], siz[N]; void dfs(int u) { dfn[u] = ++dfn[0], to[dfn[u]] = u, siz[u] = 1; for (int v : G[u]) dfs(v), siz[u] += siz[v]; } #define lb(x) (x & -x) struct BIT { int C[N]; void upd(int x, int v) { while (x <= n) (C[x] += v) %= Mod, x += lb(x); } int qry(int x) { int res = 0; while (x) (res += C[x]) %= Mod, x -= lb(x); return res; } } T[2]; signed main() { scanf("%d%d", &n, &m); for (int i = 2; i <= n; i++) { scanf("%d", &fa[i]); G[fa[i]].push_back(i); dep[i] = dep[fa[i]] + 1; } dfs(1); while (m--) { int op, x, a, b; scanf("%d%d", &op, &x); if (op == 1) { scanf("%d%d", &a, &b); if (dep[x] & 1) a = -a, b = -b; T[0].upd(dfn[x], (a - 1ll * b * dep[x]) % Mod); T[0].upd(dfn[x] + siz[x], (1ll * b * dep[x] - a) % Mod); T[1].upd(dfn[x], b), T[1].upd(dfn[x] + siz[x], -b); opr[x].push_back(make_pair(a, b)), st.insert(dfn[x]); } else if (op == 2) { int ans = (T[0].qry(dfn[x]) + 1ll * T[1].qry(dfn[x]) * dep[x]) % Mod; printf("%d\n", (dep[x] & 1 ? (Mod - ans) % Mod : (ans + Mod) % Mod)); } else if (op == 3) { auto it = st.lower_bound(dfn[x]); while (it != st.end() && *it < dfn[x] + siz[x]) { int u = to[*it]; for (auto e : opr[u]) { a = -e.first, b = -e.second; T[0].upd(dfn[u], (a - 1ll * b * dep[u]) % Mod); T[0].upd(dfn[u] + siz[u], (1ll * b * dep[u] - a) % Mod); T[1].upd(dfn[u], b), T[1].upd(dfn[u] + siz[u], -b); } opr[u].clear(), it = st.erase(it); } } } return 0; }