3 条题解
-
0
树链剖分
#include <bits/stdc++.h> using namespace std; const int MAXN = 300000 + 5; int n; vector<int> e[MAXN]; int a[MAXN]; // 旅行路线 int ans[MAXN]; // 最终答案 // 每个点的：父节点、深度、大小、重子节点 int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN]; void dfs_build(int u, int fat) { hson[u] = 0; siz[u] = 1; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fat) continue; dep[v] = dep[u] + 1; fa[v] = u; dfs_build(v, u); siz[u] += siz[v]; if (siz[v] > siz[hson[u]]) hson[u] = v; } } // 每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号 int tot, top[MAXN], dfn[MAXN], rnk[MAXN]; void dfs_div(int u, int fa) { dfn[u] = ++tot; rnk[tot] = u; if (hson[u]) { top[hson[u]] = top[u]; dfs_div(hson[u], u); for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa || v == hson[u]) continue; top[v] = v; dfs_div(v, u); } } } struct SegTree { int sum[4 * MAXN], lazy[4 * MAXN]; void up(int now) { sum[now] = sum[now * 2] + sum[now * 2 + 1]; } void down(int now, int l, int r) { if (l == r) return; int mid = (l + r) / 2; sum[now * 2] = sum[now * 2] + (mid - l + 1) * lazy[now]; sum[now * 2 + 1] = sum[now * 2 + 1] + (r - mid) * lazy[now]; lazy[now * 2] = lazy[now * 2] + lazy[now]; lazy[now * 2 + 1] = lazy[now * 2 + 1] + lazy[now]; lazy[now] = 0; } void build(int now, int l, int r) { lazy[now] = 0; if (l == r) { sum[now] = 0; //-------- return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); up(now); } void add(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { sum[now] = sum[now] + (r - l + 1) * z; lazy[now] = lazy[now] + z; return; } down(now, l, r); int mid = (l + r) / 2; if (x <= mid) add(now * 2, l, mid, x, y, z); if (y >= mid + 1) add(now * 2 + 1, mid + 1, r, x, y, z); up(now); } int query(int now, int l, int r, int x, int y) { if (x <= l && r <= y) return sum[now]; down(now, l, r); int mid = (l + r) / 2; int res = 0; if (x <= mid) res = res + query(now * 2, l, mid, x, y); if (y >= mid + 1) res = res + query(now * 2 + 1, mid + 1, r, x, y); return res; } } st; // u~v路径上点都加1 void update(int u, int v) { st.add(1, 1, tot, dfn[v], dfn[v], -1); int res = 0; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) { // v~top[v] 计入答案中 st.add(1, 1, tot, dfn[top[v]], dfn[v], 1); v = fa[top[v]]; } else { // u~top[u] 计入答案中 st.add(1, 1, tot, dfn[top[u]], dfn[u], 1); u = fa[top[u]]; } } if (dep[u] > dep[v]) swap(u, v); st.add(1, 1, tot, dfn[u], dfn[v], 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dep[1] = 1; fa[1] = 0; dfs_build(1, 0); tot = 0; top[1] = 1; dfs_div(1, 0); //-------- st.build(1, 1, tot); for (int i = 1; i <= n - 1; i++) update(a[i], a[i + 1]); for (int i = 1; i <= n; i++) cout << st.query(1, 1, tot, dfn[i], dfn[i]) << "\n"; return 0; } -
0
33DAI LV 5 (1/1) @ 2023-2-11 16:20:51
dfs里面初始化dp
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 500000; int n, m, s; vector<int> e[MAXN + 5]; int dep[MAXN + 5]; int lg[MAXN + 5]; int f[MAXN + 5][32]; void dfs(int u, int fa) { dep[u] = dep[fa] + 1; f[u][0] = fa; for (int i = 1; i <= lg[dep[u]]; i++) f[u][i] = f[f[u][i - 1]][i - 1]; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) continue; dfs(v, u); } } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1]; if (x == y) return x; for (int k = lg[dep[x]] - 1; k >= 0; --k) if (f[x][k] != f[y][k]) x = f[x][k], y = f[y][k]; return f[x][0]; } int a[312345]; int ans[312345]; void dfs2(int u, int fa) { for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) continue; dfs2(v, u); ans[u] += ans[v]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } for (int i = 1; i <= n; ++i) lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i); dep[0] = 0; dfs(1, 0); for (int i = 1; i < n; i++) { int s = a[i]; int t = a[i + 1]; int ft = f[a[i + 1]][0]; int r = lca(s, t); int fr = f[lca(s, t)][0]; if (r != t) { ans[s]++; ans[ft]++; ans[r]--; ans[fr]--; } else { ans[s]++; ans[t]--; } } dfs2(1, 0); for (int i = 1; i <= n; i++) cout << ans[i] << "\n"; cout << "\n"; return 0; } -
0
树上差分
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 500000; int n, m, s; vector<int> e[MAXN + 5]; int dep[MAXN + 5]; int lg[MAXN + 5]; int f[MAXN + 5][32]; void dfs(int u, int fa) { dep[u] = dep[fa] + 1; f[u][0] = fa; for (int i = 1; i <= lg[dep[u]]; i++) f[u][i] = f[f[u][i - 1]][i - 1]; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) continue; dfs(v, u); } } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1]; if (x == y) return x; for (int k = lg[dep[x]] - 1; k >= 0; --k) if (f[x][k] != f[y][k]) x = f[x][k], y = f[y][k]; return f[x][0]; } int a[312345]; int ans[312345]; void dfs2(int u, int fa) { for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) continue; dfs2(v, u); ans[u] += ans[v]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } for (int i = 1; i <= n; ++i) lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i); dep[0] = 0; dfs(1, 0); for (int i = 1; i < n; i++) { int s = a[i]; int t = a[i + 1]; int ft = f[a[i + 1]][0]; int r = lca(s, t); int fr = f[lca(s, t)][0]; if (r != t) { ans[s]++; ans[ft]++; ans[r]--; ans[fr]--; } else { ans[s]++; ans[t]--; } } dfs2(1, 0); for (int i = 1; i <= n; i++) cout << ans[i] << "\n"; cout << "\n"; return 0; }
- 1