Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
30752 gaochunzhen 【S】T2 C++ 运行超时 66 3009 MS 26448 KB 2037 2024-07-30 13:14:42

Tests(12/18):


#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9, Mod = 1e9 + 7; vector<int> G[N]; int n, m, fa[N], dep[N]; namespace sub1 { int dfn[N], siz[N]; void dfs(int u) { dfn[u] = ++dfn[0], 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, x += lb(x); } int get(int x) { int res = 0; while (x) res += C[x], x -= lb(x); return res; } int qry(int x) {return x ? get(x) - get(x - 1) : 0;} void upd(int x) { upd(x + 1, get(x + 1) - qry(x + 1)); upd(x, -get(x - 1) - qry(x)); } } T; int opr[N][2]; void Main() { dfs(1); while (m--) { int op, x, a, b; scanf("%d%d", &op, &x); if (op == 1) { scanf("%d%d", &a, &b); if (T.get(dfn[x])) opr[x][0] = opr[x][1] = 0; opr[x][0] = (opr[x][0] + a + Mod) % Mod; opr[x][1] = (opr[x][1] + b + Mod) % Mod; T.upd(dfn[x]); } else if (op == 2) { int u = x, ans = 0; while (u) { if (!T.get(dfn[u])) { int now = (opr[u][0] + 1ll * opr[u][1] * (dep[x] - dep[u])) % Mod; ans = ((dep[x] - dep[u]) & 1 ? (ans - now + Mod) % Mod : (ans + now) % Mod); } u = fa[u]; } printf("%d\n", ans); } else if (op == 3) { T.upd(dfn[x], 1), T.upd(dfn[x] + siz[x], -1); } } } } 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; } sub1::Main(); return 0; }


测评信息: