目录
- 题目答疑
树剖std
- @ 2026-4-12 11:09:20
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
int n, m, rt, cur;
ll a[N], t[N * 4], lz[N * 4];
int sz[N], f[N][20], dep[N], sn[N], tp[N], dfn[N], rk[N];
vector<int> g[N];
void d1(int u, int p, int d) {
sz[u] = 1;
f[u][0] = p;
dep[u] = d;
for (int i = 1; i < 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];
for (int v : g[u]) {
if (v == p) continue;
d1(v, u, d + 1);
sz[u] += sz[v];
if (sz[v] > sz[sn[u]]) sn[u] = v;
}
}
void d2(int u, int t) {
tp[u] = t;
dfn[u] = ++cur;
rk[cur] = u;
if (sn[u]) d2(sn[u], t);
for (int v : g[u]) {
if (v == f[u][0] || v == sn[u]) continue;
d2(v, v);
}
}
void bld(int p, int l, int r) {
if (l == r) {
t[p] = a[rk[l]];
return;
}
int mid = (l + r) >> 1;
bld(p << 1, l, mid);
bld(p << 1 | 1, mid + 1, r);
t[p] = t[p << 1] + t[p << 1 | 1];
}
void psd(int p, int l, int r) {
if (lz[p]) {
int mid = (l + r) >> 1;
lz[p << 1] += lz[p];
lz[p << 1 | 1] += lz[p];
t[p << 1] += lz[p] * (mid - l + 1);
t[p << 1 | 1] += lz[p] * (r - mid);
lz[p] = 0;
}
}
void upd(int p, int l, int r, int ql, int qr, ll v) {
if (ql > qr) return;
if (ql <= l && r <= qr) {
t[p] += v * (r - l + 1);
lz[p] += v;
return;
}
psd(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) upd(p << 1, l, mid, ql, qr, v);
if (qr > mid) upd(p << 1 | 1, mid + 1, r, ql, qr, v);
t[p] = t[p << 1] + t[p << 1 | 1];
}
ll ask(int p, int l, int r, int ql, int qr) {
if (ql > qr) return 0;
if (ql <= l && r <= qr) return t[p];
psd(p, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid) res += ask(p << 1, l, mid, ql, qr);
if (qr > mid) res += ask(p << 1 | 1, mid + 1, r, ql, qr);
return res;
}
int lca(int u, int v) {
while (tp[u] != tp[v]) {
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
u = f[tp[u]][0];
}
return dep[u] < dep[v] ? u : v;
}
int get(int u, int v) {
for (int i = 19; i >= 0; i--) {
if (dep[f[v][i]] > dep[u]) v = f[v][i];
}
return v;
}
void mP(int u, int v, ll k) {
while (tp[u] != tp[v]) {
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
upd(1, 1, n, dfn[tp[u]], dfn[u], k);
u = f[tp[u]][0];
}
if (dep[u] > dep[v]) swap(u, v);
upd(1, 1, n, dfn[u], dfn[v], k);
}
ll qP(int u, int v) {
ll res = 0;
while (tp[u] != tp[v]) {
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
res += ask(1, 1, n, dfn[tp[u]], dfn[u]);
u = f[tp[u]][0];
}
if (dep[u] > dep[v]) swap(u, v);
res += ask(1, 1, n, dfn[u], dfn[v]);
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++) {
int p; cin >> p;
g[p].push_back(i);
g[i].push_back(p);
}
d1(1, 0, 1);
d2(1, 1);
bld(1, 1, n);
rt = 1;
cin >> m;
while (m--) {
int op, u, v;
ll k;
cin >> op;
if (op == 1) {
cin >> rt;
} else if (op == 2) {
cin >> u >> v >> k;
mP(u, v, k);
} else if (op == 3) {
cin >> u >> k;
if (u == rt) {
upd(1, 1, n, 1, n, k);
} else {
int lc = lca(u, rt);
if (lc != u) {
upd(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, k);
} else {
int s = get(u, rt);
upd(1, 1, n, 1, dfn[s] - 1, k);
upd(1, 1, n, dfn[s] + sz[s], n, k);
}
}
} else if (op == 4) {
cin >> u >> v;
cout << qP(u, v) << "\n";
} else {
cin >> u;
if (u == rt) {
cout << ask(1, 1, n, 1, n) << "\n";
} else {
int lc = lca(u, rt);
if (lc != u) {
cout << ask(1, 1, n, dfn[u], dfn[u] + sz[u] - 1) << "\n";
} else {
int s = get(u, rt);
cout << ask(1, 1, n, 1, dfn[s] - 1) + ask(1, 1, n, dfn[s] + sz[s], n) << "\n";
}
}
}
}
return 0;
}
0 条评论
目前还没有评论...
京公网安备11010802045784号
YIZHIYANG 一只羊 LV 10