题目描述
(\)
(\)
(Solution)
这题目描述就离谱bushi
考场翻来覆去读了几遍题没看懂kkkkk
大概翻译一下题目意思就是：给你一个序列 (d)，如果当前读到 (d_i) ，就跳到 (d_i + a_i) ，目标是最后正好跳到 (n + 1) ；对于 (a_i) 可以修改为 (a_i +- y) ，修改代价为 (y(y >= 0)) ；求最小代价。现在有一棵树，对于从根节点到叶子节点的每条链都看做一个序列，求出所有最小代价。
感谢(mathtt{I})(mathtt{color{red}{makf}}) 给我讲了好几遍这道题，终于明白力！！！
(\)
考虑只在序列上做
设 (dp[i]) 表示跳到了 (i) 的时候的最小代价
若当前 (dp[i]) 已知，设 (j = i + a_i) ，则 (dp[j] = min(dp[j], dp[i])) ，因为可以直接跳到，不需要修改 (a_i)
那么来考虑修改，则 $$dp[j - x] = min(dp[j - x], dp[j] + j - x)$$ $$dp[j + x] = min(dp[j + x], dp[j] + x - j)$$
于是可以 (O(n^2)) 顺利解决
(\)
接下来考虑优化
先只考虑 (dp[j] = min(dp[j], dp[i] + i - j)) 这一种转移（就是上面写的那个式子，改了一下变量），往后推的和这个差不多
想把 (O(n^2)) 降为 (O(nlog n)) ，正确做法是在脑子里随便找一种数据结构试试可不可行
直接给结论：开一颗线段树，在第 (i) 个叶子节点存的是 (tree[i] = dp[i] + i) ，维护最小值
为什么要存这个？其实很巧妙
看看上面的转移方程，如果先不考虑取 (min)，即 $$dp[j] = dp[i] + i - j$$
得到了 (dp[j]) 后我们要存进线段树中，将方程两边加上 (j) 就变成了 $$tree[j] = dp[j] + j = dp[i] + i - j + j = dp[i] + i = tree[i]$$
发现直接可以用线段树中的 (tree[i]) 更新 (tree[j]) ！
(\)
考虑更新的顺序
由于每个点只能往后跳，所以可以直接按照序列顺序更新
简单证明：若现在已经更新到了 (i) ，假设点 (j > i) ，若想用 (j + a_j) 更新 (i) ，相当于把 (a_j) 更改为 (i - j) ，而 (a_j) 不可能是负的，所以无法更新
(\)
考虑在树上做
直接深搜，维护一个线段树，在回溯时撤销操作即可
多写一句关于在树上维护某个数据结构进行撤销操作怎么做
以下所有原数组指的是全局变量的数据结构
(1.) 直接开一个数组存下这个原数组，再把原数组进行更新，最后再把这个数组的值赋给原数组
(2.) 对于树状数组/线段树，如果是单点修改，那就最多只有 (log n) 个点更改，保存这些点即可
(3.) 对于树状数组/线段树，如果是单点修改，可以直接存下在原数组里这个点的值，撤销就用这个值修改一下（比如说在这个点上 (+3) ，撤销就在这个点上 (-3) ）
(\)
完结撒花✿✿ヽ(°▽°)ノ✿
(update(2020.7.2):) 关于线段树中到了叶子节点直接赋值而不用取 (min) ，是因为在修改之前就判断了是否大于当前的值，所以一定要修改。被踩辣 (kk)
(\)
(\)
(Code)
#include<bits/stdc++.h>
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1| 1)
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read();
const int N = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int n, x, y, m;
int a[N], ans[N], dp[N], tree[2][N << 2];
int head[N], cnt, ver[N << 1], nxt[N << 1];
void add(int x, int y){ver[++ cnt] = y, nxt[cnt] = head[x], head[x] = cnt;}
void update(int l, int r, int k, int pos, int v, int op)
{
if(l == r && l == pos) {tree[op][k] = v; return;}
if(pos <= mid) update(l, mid, ls, pos, v, op);
else update(mid + 1, r, rs, pos, v, op);
tree[op][k] = min(tree[op][ls], tree[op][rs]);
}
int query(int l, int r, int k, int x, int y, int op)
{
if(l >= x && r <= y) return tree[op][k];
int res = inf;
if(x <= mid) res = min(res, query(l, mid, ls, x, y, op));
if(y > mid) res = min(res, query(mid + 1, r, rs, x, y, op));
return res;
}
void dfs(int x, int dep)
{
int tmp1 = -inf, tmp2 = -inf, u = a[x] + dep, now = dp[dep - 1] + 1;
if(x != 1)
{
int b1 = query(1, n, 1, u, u, 0), b2 = query(1, n, 1, u, u, 1);
if(b1 > now - u) tmp1 = b1, update(1, n, 1, u, now - u, 0);
if(b2 > now + u) tmp2 = b2, update(1, n, 1, u, now + u, 1);
dp[dep] = min(query(1, n, 1, 1, dep, 0) + dep, query(1, n, 1, dep, n, 1) - dep);
}
for(int i = head[x]; i; i = nxt[i]) dfs(ver[i], dep + 1);
if(! head[x]) ans[++ m] = dp[dep];
if(tmp1 != -inf) update(1, n, 1, u, tmp1, 0);
if(tmp2 != -inf) update(1, n, 1, u, tmp2, 1);
}
int main()
{
n = read();
F(i, 1, n)
{
a[i] = read(), y = read();
F(j, 1, y) x = read(), add(i, x);
}
memset(tree, 0x3f, sizeof(tree));
dfs(1, 1), sort(ans + 1, ans + m + 1);
F(i, 1, m) printf("%d
", ans[i]);
return 0;
}
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}