\(\color{red}(-114514)\) P1424 小鱼的航程（改进版）
- 有一只小鱼，它平日每天游泳 \(250\) 公里，周末休息（实行双休日)，假设从周 \(x\) 开始算起，过了 \(n\) 天以后，小鱼一共累计游泳了多少公里呢？
太难了，先咕咕咕。
\(\color{red}(1)\) UOJ387 To Do Tree
-
有 \(n\) 个任务，做第 \(i\) 个任务需要先做第 \(f_i\) 个任务。依赖关系形成了一棵树，树根为任务 \(1\)。每天你可以完成 \(m\) 个任务，这 \(m\) 个任务之间不能有依赖关系。求最少的完成所有任务的天数。
-
\(n \le 10^5\)。
贪心策略是每次找子树最大的任务做。
实现上维护一个堆，存储当前哪些任务可以做但还没做，按照子树大小从大到小排序。每次取堆中前 \(m\) 大即可。
$\color{blue}\text{Code}$
struct Tree {
vector<int> g[N];
void add(int a, int b) { g[a].push_back(b); }
vector<int> operator [](const int &u) const { return g[u]; }
}T;
int n, m, fa[N], sz[N];
void Luogu_UID_748509() {
fin >> n >> m;
fill(sz + 1, sz + n + 1, 1);
for (int i = 2; i <= n; ++ i ) {
fin >> fa[i];
T.add(fa[i], i);
}
for (int i = n; i >= 2; -- i ) {
sz[fa[i]] += sz[i];
}
priority_queue<PII> q;
q.emplace(sz[1], 1);
int tmp = 0;
vector<vector<int> > ans;
while (tmp < n) {
vector<int> vec;
for (int i = 1; i <= m && q.size(); ++ i ) {
vec.emplace_back(q.top().second);
q.pop();
++ tmp;
}
ans.emplace_back(vec);
for (int u : vec) {
for (int v : T[u]) {
q.emplace(sz[v], v);
}
}
}
fout << ans.size() << '\n';
for (vector<int> t : ans) {
fout << t.size() << ' ' << t;
}
}
\(\color{red}(2)\) P4211 [LNOI2014] LCA
- 给定一颗 \(n\) 的节点的树。\(m\) 次询问 \(\sum_{i=l}^r \operatorname{depth}_{\operatorname{lca}(i, z)}\)。
- \(n, m \le 5 \times 10^4\)。
考虑几个弱化版本：
- \(m\) 次询问 \(\operatorname{depth}_{\operatorname{lca}(x, y)}\)。
显然可以用朴素做法。这里的做法是这样的：
- 将 \(x\) 到根上每个点加 \(1\)，那么 \(y\) 到根的点权和即答案。原因是 \(x, y\) 到根的公共路径长度就是它们最近公共祖先的深度。
- 实现用树剖解决。
$\color{blue}\text{Code}$
while (m -- ) {
int x, y;
scanf("%d%d", &x, &y);
modify(1, x, 1); // 1 到 x 的路径加一
printf("%d\n", query(1, y)); // 1 到 y 的路径和
modify(1, x, -1); // 清空
}
- 单次询问 \(\sum_{i=l}^r \operatorname{depth}_{\operatorname{lca}(i, z)}\)。
显然也可以用朴素做法。这里我们延续上一问的做法：
- 对于所有 \(i \in [l, r]\)，将 \(i\) 到根上每个点累加 \(1\)，那么 \(z\) 到根的点权和即答案。
$\color{blue}\text{Code}$
int l, r, z;
scanf("%d%d%d", &l, &r, &z);
for (int i = l; i <= r; ++ i ) modify(1, i, 1); // 1 到 i 的路径加一
printf("%d\n", query(1, z)); // 1 到 z 的路径和
- \(m\) 次询问 \(\sum_{i=\color{red}\mathbf1}^r \operatorname{depth}_{\operatorname{lca}(i, z)}\)。
显然不能用朴素做法了。做法是这样的：
- 考虑离线所有询问。vector 以 \(r\) 做下标，存储每个询问的编号和 \(z\)。即
vec[r].push_back(make_pair(i, z))。 - 枚举 \(i = (1, 2, \dots, n)\)，并每次将 \(i\) 到根上每个点累加 \(1\)。
- 然后访问 vector 的 \(i\) 中的所有元素 \((j, z)\)，我们将 \(z\) 到根的点权和累加到询问 \(j\) 的答案中。
$\color{blue}\text{Code}$
int res[N]; // 第 i 问的答案
vector<pair<int, int> > vec[N];
for (int i = 1; i <= m; ++ i ) {
scanf("%d%d", &a[i].r, &a[i].z);
vec[a[i].r].push_back({i, a[i].z});
}
for (int i = 1; i <= n; ++ i ) {
modify(1, i, 1); // 1 到 i 的路径加一
for (pair<int, int> t : vec[i]) {
int a = t.first, b = t.second;
res[a] += query(1, b); // 1 到 i 的路径和
}
}
for (int i = 1; i <= n; ++ i ) printf("%d\n", res[i]);
- \(m\) 次询问 \(\sum_{i=l}^r \operatorname{depth}_{\operatorname{lca}(i, z)}\)，即本题。
上一问差分即可。
$\color{blue}\text{Code}$
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50010, M = N << 1;
int n, m, fa[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
vector<pair<int, int> > vec[N];
int res[N];
int dep[N], top[N], son[N], id[N], cnt, sz[N];
void dfs1(int u) {
dep[u] = dep[fa[u]] + 1;
sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs1(v);
sz[u] += sz[v];
if (sz[u] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
id[u] = ++ cnt;
if (son[u]) {
dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v != son[u]) dfs2(v, v);
}
}
}
struct Tree {
int l, r, v, tag;
}tr[N << 2];
void pushup(int u) {
tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
void calc(int u, int k) {
tr[u].tag += k;
tr[u].v += k * (tr[u].r - tr[u].l + 1);
}
void pushdown(int u) {
calc(u << 1, tr[u].tag), calc(u << 1 | 1, tr[u].tag);
tr[u].tag = 0;
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0};
if (l != r) {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void modify(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) calc(u, 1);
else {
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= mid) modify(u << 1, l, r);
if (r > mid) modify(u << 1 | 1, l, r);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int res = 0, mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
void Tree_modify(int a, int b) {
while (top[a] != top[b]) {
if (dep[top[a]] < dep[top[b]]) swap(a, b);
modify(1, id[top[a]], id[a]);
a = fa[top[a]];
}
if (dep[a] > dep[b]) swap(a, b);
modify(1, id[a], id[b]);
}
int Tree_query(int a, int b) {
int res = 0;
while (top[a] != top[b]) {
if (dep[top[a]] < dep[top[b]]) swap(a, b);
res += query(1, id[top[a]], id[a]);
a = fa[top[a]];
}
if (dep[a] > dep[b]) swap(a, b);
return res + query(1, id[a], id[b]);
}
signed main() {
memset(h, -1, sizeof h);
scanf("%lld%lld", &n, &m);
for (int i = 2; i <= n; ++ i ) {
scanf("%lld", fa + i);
fa[i] ++ ;
add(fa[i], i);
}
for (int i = 1; i <= m; ++ i ) {
int l, r, z;
scanf("%lld%lld%lld", &l, &r, &z);
vec[1 + r].push_back({i, 1 + z});
vec[l].push_back({-i, 1 + z});
}
dfs1(1), dfs2(1, 0);
build(1, 1, n);
for (int i = 1; i <= n; ++ i ) {
Tree_modify(1, i);
for (pair<int, int> t : vec[i]) {
int a = abs(t.first), b = t.second;
int k = t.first > 0 ? 1 : -1;
res[a] += k * Tree_query(1, b);
}
}
for (int i = 1; i <= m; ++ i ) printf("%lld\n", res[i] % 201314);
return 0;
}
\(\color{red}(3)\) P2680 [NOIP2015 提高组] 运输计划
- 给定一棵 \(n\) 个点的树，边有边权 \(w_i\)。给定 \(m\) 条路径 \((u_i,v_i)\)。你可以选择一条边，将其边权变为 \(0\)。最小化这 \(m\) 条路径长度的最大值。
- \(n, m \le 3 \times 10^5\)。
二分答案 \(mid\)。
对于原来路径长度 \(\le mid\)，我们无需考虑。换句话说，我们需要考虑的是长度 \(> mid\) 的路径。
对于这些路径而言，我们希望通过仅改变树上一条边，让这些路径的长度都变得 \(\le mid\)。显然这条边需要是这些路径的交，而且是交中边权最大的。
找路径交可以用树上差分的套路。
找到这条设为 \(0\) 的边后简单判断一下即可。
$\color{blue}\text{Code}$
#include <bits/stdc++.h>
using namespace std;
const int N = 300010, M = N * 2, K = 19;
int n, m;
int h[N], e[M], ne[M], idx, w[M];
int fa[N][K], dep[N], dis[N];
int seq[N], cnt;
struct Path
{
int a, b, p, d;
}q[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] =c, h[a] = idx ++ ;
}
void dfs(int u, int F, int D)
{
seq[cnt ++ ] = u;
dep[u] = D;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == F) continue;
fa[j][0] = u;
for (int k = 1; k < K; ++ k )
fa[j][k] = fa[fa[j][k - 1]][k - 1];
dis[j] = dis[u] + w[i];
dfs(j, u, D + 1);
}
}
int lca(int a, int b)
{
if (dep[a] < dep[b]) swap(a, b);
for (int k = K - 1; ~k; -- k )
if (dep[fa[a][k]] >= dep[b])
a = fa[a][k];
if (a == b) return a;
for (int k = K - 1; ~k; -- k )
if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
return fa[a][0];
}
int sum[N];
bool chk(int mid)
{
memset(sum, 0, sizeof sum);
int c = 0, mx = 0;
for (int i = 0; i < m; ++ i )
{
int a = q[i].a, b = q[i].b, p = q[i].p, d = q[i].d;
if (d > mid)
{
++ c;
mx = max(mx, d);
++ sum[a], ++ sum[b], sum[p] -= 2;
}
}
if (!c) return true;
for (int i = n - 1; ~i; -- i )
{
int j = seq[i];
sum[fa[j][0]] += sum[j];
}
for (int i = 1; i <= n; ++ i )
if (sum[i] == c && mx - dis[i] + dis[fa[i][0]] <= mid)
return true;
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i < n; ++ i )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1, 1);
for (int i = 0; i < m; ++ i )
{
int a, b;
cin >> a >> b;
int p = lca(a, b);
int d = dis[a] + dis[b] - dis[p] * 2;
q[i] = {a, b, p, d};
}
int l = 0, r = 3e8;
while (l < r)
{
int mid = l + r >> 1;
if (chk(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
\(\color{red}(4)\) P2486 [SDOI2011] 染色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 给定一棵 \(n\) 个点的树，每个点上有一个颜色。你需要支持两种操作：
- 将一条链 \((x,y)\) 上的点全部染成颜色 \(c\)。
- 询问一条链 \((x,y)\) 上的点的颜色组成了几个颜色段。
- \(n \le 10^5\)。
好题！
-
16:09：写完，RE
-
2 min later：计算重儿子时
son[u] = sz[v]，但输出极大值 2088774347。 -
2 min later：线段树初始化没有用树剖后的编号
id[l]而是l。 -
114514 min later：tmd 不做了。