【文件夹合并——树链剖分，树状数组】

题目

复杂度

代码 #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5 + 10; const int M = 1e6 + 10; int n, m; vector<int> sub[N]; // 子文件夹 ll d[N]; // 数据量 int h[N], e[M], ne[M], idx; // 链式前向星 int dep[N], sz[N], son[N], dfn[N], fa[N], top[N], id[N], cnt; // 树链剖分 int tr[N]; // 树状数组 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs1(int u) { sz[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa[u]) continue; // fa[root] = 0; dep[j] = dep[u] + 1; fa[j] = u; dfs1(j); sz[u] += sz[j]; if (sz[j] > sz[son[u]]) son[u] = j; } } void dfs2(int u, int t) { dfn[u] = ++cnt; id[cnt] = u; top[u] = t; if (!son[u]) return; else dfs2(son[u], t); for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa[u] || j == son[u]) continue; dfs2(j, j); } } ll query(int x) { ll retv = 0; for (; x; x -= x & -x) retv += tr[x]; return retv; } ll query(int l, int r) { return query(r) - query(l - 1); } void modify(int x, int v) { for (; x <= n; x += x & -x) tr[x] += v; } ll nquery(int a, int b) { ll retv = 0; while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); retv += query(dfn[top[a]], dfn[a]); a = fa[top[a]]; } if (dep[a] > dep[b]) swap(a, b); retv += query(dfn[a], dfn[b]); return retv; } void nmodify(int x, int v) { modify(dfn[x], v); } int main() { ios::sync_with_stdio(0); cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 2; i <= n; i++) { int f; cin >> f; sub[f].push_back(i); add(f, i); add(i, f); } for (int i = 1; i <= n; i++) cin >> d[i]; dfs1(1); dfs2(1, 1); for(int i = 1; i <= n; i++) nmodify(i, 1); while (m--) { int op, x; cin >> op >> x; if (op == 1) { vector<int> t; for (int i : sub[x]) { d[x] += d[i]; nmodify(i, -1); for (int j : sub[i]) t.push_back(j); } sub[x] = t; cout << sub[x].size() << ' ' << d[x] << '\n'; } else if (op == 2) cout << nquery(1, x) << '\n'; } }