## 好冷好热好冷好热
#贪心 #模拟
首先可以想到很显然的解法，就是设计状态 $(i,j)$ 表示如果第 $i$ 秒温度为 $j$，前 $i$ 秒是否均满足条件。当然这个是会炸掉的。
不难发现后面的 $j$ 实际上可取的值是一个区间（所有人的温度要求的交和可能的温度的交）。所以我们只需要维护区间就行了。
但是枚举 $i$ 还是会炸。所以考虑对时间进行离散化，离散化之后就只需要枚举最多 $n$ 个 $i$。如果当前 $i$ 与上一个 $i$ 的差值为 $\Delta i$，那么区间就变成 $[l-\Delta i,r+\Delta i]$。再对当前 $i$ 对应的所有要求温度区间取交集即可。如果取完变空集就不满足条件。
```cpp
#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("temp.in");
ofstream cout("temp.out");
LL l[kMaxN], h[kMaxN], t[kMaxN], val[kMaxN], T, n, m, k;
vector<pair<LL, LL>> v[kMaxN];
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> T; T; T--) {
cin >> n >> m;
fill(v + 1, v + k + 1, vector<pair<LL, LL>>());
k = 0;
for (LL i = 1; i <= n; i++) {
cin >> t[i] >> l[i] >> h[i];
val[++k] = t[i];
}
sort(val + 1, val + k + 1);
k = unique(val + 1, val + k + 1) - val - 1;
for (LL i = 1; i <= n; i++) {
t[i] = lower_bound(val + 1, val + k + 1, t[i]) - val;
v[t[i]].emplace_back(l[i], h[i]);
}
[]() {
LL l = m, r = m;
for (LL i = 1; i <= k; i++) {
l -= val[i] - val[i - 1];
r += val[i] - val[i - 1];
for (const auto &j : v[i]) {
if (r < j.first || l > j.second) {
cout << "NO\n";
return;
}
l = max(l, j.first);
r = min(r, j.second);
}
if (l > r) {
cout << "NO\n";
}
}
cout << "YES\n";
}();
}
return 0;
}
```
## 杀戮尖塔
#线段树 #二分 #倍增 #树链剖分
首先这道题目有多个不同的遗物，以区间或路径为基础很难处理这些不同的遗物。所以考虑分遗物处理区间。
对于 $x$ 到 $1$ 的路径，很显然我们可以写一个二分，二分出最下方一个点 $i$ 使得 $i\sim x$ 的路径上正好有一个遗物，开 $n$ 棵动态开点线段树用于判断。当然，预处理倍增父亲后直接倍增就行了。
这样子是不好做的，因为我们无法快速查询 $x$ 到 $x$ 上方的祖先之间是否有 $y$ 存在。考虑做树剖，先把 $x$ 往上跳若干条没有 $y$ 存在的链，然后在剩下的那条有 $y$ 的链上做二分或者倍增。时间复杂度 $\mathcal O(q\log^2 n)$。
这样子的在线做法的时间复杂度还是太高了。考虑离线，对于每个 $i$ 可能作为哪些 $x$ 的答案。不难发现每个 $i$ 可能给 $i$ 子树中的任意点做贡献，但是对于 $x$ 它要求深度最大的 $i$。所以按照深度枚举 $i$ 然后对指定线段树上 $i$ 进行子树覆盖即可。时间复杂度 $\mathcal O((q+n)\log_2 n)$。
当然我写的在线做法。
```cpp
#include <fstream>
#include <vector>
using namespace std;
const int kMaxN = 1e5 + 5, kLog = 20;
ifstream cin("slay.in");
ofstream cout("slay.out");
struct Node {
int lc, rc, sum;
} tr[kLog * kMaxN];
int rt[kMaxN], fa[kMaxN], dp[kMaxN][kLog], dfn[kMaxN], top[kMaxN], dep[kMaxN], siz[kMaxN], son[kMaxN], n, q, cnt, tim;
vector<int> e[kMaxN];
void modify(int &p, int l, int r, int x) {
if (!p) {
p = ++cnt;
}
tr[p].sum = 1;
if (l == r) {
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(tr[p].lc, l, m, x);
} else {
modify(tr[p].rc, m + 1, r, x);
}
}
int query(int p, int l, int r, int s, int t) {
if (!p || s > t) {
return 0;
}
if (s <= l && r <= t) {
return tr[p].sum;
}
int m = (l + r) / 2, res = 0;
if (s <= m) {
res |= query(tr[p].lc, l, m, s, t);
}
if (m < t) {
res |= query(tr[p].rc, m + 1, r, s, t);
}
return res;
}
void dfs1(int x, int f) {
dep[x] = dep[f] + 1;
fa[x] = f;
siz[x] = 1;
dp[x][0] = f;
for (int i = 1; i < kLog; i++) {
dp[x][i] = dp[dp[x][i - 1]][i - 1];
}
for (int i : e[x]) {
if (i == f) {
continue;
}
dfs1(i, x);
siz[x] += siz[i];
if (siz[i] > siz[son[x]]) {
son[x] = i;
}
}
}
void dfs2(int x, int t) {
top[x] = t;
dfn[x] = ++tim;
if (son[x]) {
dfs2(son[x], t);
}
for (int i : e[x]) {
if (i == fa[x] || i == son[x]) {
continue;
}
dfs2(i, i);
}
}
int jump(int x, int y) {
for (int i = 0; i < kLog; i++) {
if (y & (1 << i)) {
x = dp[x][i];
}
}
return x;
}
int query(int x, int y) {
for (; x && !query(rt[y], 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]]) { }
if (!x) {
return -1;
}
int res = 0;
for (int l = 0, r = dep[x] - 1; l <= r; ) {
int m = (l + r) / 2, p = jump(x, m);
if (query(rt[y], 1, n, dfn[p], dfn[x])) {
res = p;
r = m - 1;
} else {
l = m + 1;
}
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 2, x; i <= n; i++) {
cin >> x;
e[x].push_back(i);
}
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1, k; i <= n; i++) {
cin >> k;
for (int x; k; k--) {
cin >> x;
modify(rt[x], 1, n, dfn[i]);
}
}
cin >> q;
for (int x, y; q; q--) {
cin >> x >> y;
cout << query(x, y) << '\n';
}
return 0;
}
```
## 故障机器人
#广度优先搜索
首先机器人在路径长度超过 $d$ 之后会炸掉，炸掉后对人没有影响，但是人只要被任意一个机器人的任意一种走法抓住就会死掉，所以我们直接规定所有机器人都不能炸掉就行了（保证每个机器人路径长度始终小于等于 $d$）。
我们需要判断如果在 $t$ 时刻到 $i$ 点的话是否又被机器人抓到的可能性，如果有就不能在这个时刻走到 $i$。具体来说，如果 $k$ 个机器人当中有任何一个可以正好在 $t$ 时刻到 $i$，$i$ 就走不了。
然而，机器人可以在两个点之间反复横跳（如果已走步数小于 $d$ 的话）。所以，我们只需要判断机器人是否有走到 $i$ 的路径且这个路径长与 $t$ 同奇偶，如果还路径长小于等于 $t$ 的话，就是可以走到 $i$ 的。 （如果 $t$ 超出了 $d$，就把 $t$ 变成小于等于 $d$ 且和 $t$ 同奇偶的数）这是奇偶最短路的模板。
现在我们的主要问题就是对于 $k$ 个怪物跑单源最短路太慢了。不过我们只需要判断是否有一个怪物可到达即可，这预示着我们可以对所有怪物一起处理。即多个源点的奇偶最短路。
处理完所有点的是能否走的情况后，我们开始构造方案。对于一个点 $i$，如果有多个同奇偶的 $t$ 可以经过这个 $i$，那么一定是 $t$ 最小的更优，因为在所有同奇偶的 $t$ 当中，$t$ 越大可以到达的点一定是更多的，这使得我们的行动愈发受限。
所以对 $1$ 的起点跑奇偶最短路，辅佐对能否被怪物干死的判断，即可得到一条 $1\sim n$ 的路径。在奇数长路径和偶数长路径中选更短的那条即可。
最后是输出答案。本题的 std 书写错误，它是反着求最小字典序的（也就是 $1\rightarrow 3\rightarrow 2\rightarrow 4$ 比 $1\rightarrow 2\rightarrow 3\rightarrow 4$ 更优；而我的代码正确地处理了正着的最小字典序。因为 std 的错误处理，导致我 WA 了 $10$ 分的测试点。现在展现的是我正确处理了字典序的代码（实际 $90$ 分）：
```cpp
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("defect.in");
ofstream cout("defect.out");
const int kMaxN = 1e5 + 5;
int dis[kMaxN][2], len[kMaxN][2], a[kMaxN], f[kMaxN], n, m, d, k;
vector<int> e[kMaxN], p[kMaxN][2], g[kMaxN];
queue<pair<int, int>> q;
void bfs() {
fill(dis[0], dis[0] + 2 * kMaxN, 1e9);
for (int i = 1; i <= k; i++) {
dis[a[i]][0] = 0;
q.emplace(a[i], 0);
}
for (; q.size(); q.pop()) {
auto t = q.front();
for (int i : e[t.first]) {
if (dis[t.first][t.second] + 1 < dis[i][t.second ^ 1]) {
dis[i][t.second ^ 1] = dis[t.first][t.second] + 1;
q.emplace(i, t.second ^ 1);
}
}
}
}
// 在 t 时刻，x 是否会被干掉
bool check(int x, int t) {
if (t % 2 == d % 2) {
t = min(t, d);
} else {
t = min(t, d - 1);
}
return dis[x][t % 2] <= t;
}
void solve() {
if (check(1, 0)) {
cout << "-1\n";
exit(0);
}
fill(len[0], len[0] + 2 * kMaxN, 1e9);
for (q.emplace(1, 0), len[1][0] = 0; q.size(); q.pop()) {
auto t = q.front();
for (int i : e[t.first]) {
if (!check(i, len[t.first][t.second] + 1)) {
if (len[t.first][t.second] + 1 < len[i][t.second ^ 1]) {
p[i][t.second ^ 1].clear();
p[i][t.second ^ 1].push_back(t.first);
len[i][t.second ^ 1] = len[t.first][t.second] + 1;
q.emplace(i, t.second ^ 1);
} else if (len[t.first][t.second] + 1 == len[i][t.second ^ 1]) {
p[i][t.second ^ 1].push_back(t.first);
}
}
}
}
}
void paint(int x, int b) {
if (f[x]) {
return;
}
f[x] = 1;
for (int i : p[x][b]) {
g[i].push_back(x);
paint(i, b ^ 1);
}
}
void print() {
for (int x = 1; x != n; ) {
cout << x << ' ';
x = *min_element(g[x].begin(), g[x].end());
}
cout << n << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> d;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i];
}
bfs();
solve();
if (len[n][0] == 1e9 && len[n][1] == 1e9) {
cout << "-1\n";
return 0;
}
if (len[n][0] < len[n][1]) {
cout << len[n][0] << '\n';
paint(n, 0);
} else {
cout << len[n][1] << '\n';
paint(n, 1);
}
print();
return 0;
}
```
## 树上纯树
#李超线段树 #树形dp
考虑最简单的动态规划：设 $dp_i$ 表示 $i$ 到其子树中的任意叶子节点需要的最小费用。那么对于已经是叶子节点的 $i$，有 $dp_i=0$；否则枚举子树中的任意节点 $j$ $(j\ne i)$，求 $\min(a_ib_j+dp_j)$。
时间复杂度 $\mathcal O(n^2)$，可以写一个启发式合并。然后……就不会优化了。需要用李超线段树解决子树的问题，然后线段树合并。但是我不会。