## 日记和最短路
首先一条边的边权字符串长度不一致很难搞，因为拼起来之后会错位，导致我们无法选择字典序最小的。因此可以将不同长度的字符串拆成多个字符，然后建虚点，这样就可以保证每条边i上边权都是一个字符。
现在对于第二问已经很好解决了。分层跑 BFS，每次让所有节点一起往后走一条边，但是必须满足走的边是所有可走的边当中字典序最小的那个。
这样我们每一步都走的字典序最小的，也就满足我们的任意一条路径任意前缀最小，也就有了答案最小。还原答案就是记录转移的上一个节点然后反向还原即可。
- [!] 需要注意的一条边只有在终点可以到达 $n$ 时才是有效的，其余直接忽略。我们是在所有有效的边当中选取字典序最小的若干条。
- [n] 所以我们需要需要建反向边，从 $n$ 开始跑 DFS 或 BFS 找到所有可以到 $n$ 的节点。
- [c] 赛时我建反向边写错了，但是样例全过，最终直接炸缸。
然后是第一问，其实大差不差。同样是在反向图上先跑一遍 BFS 求出任意节点到 $n$ 的最短路。然后同样套用上面的板子，但是第一比较关键字改成到 $n$ 的距离，其次才是字典序。这样我们就成功完成了两个询问。
最后就是漫长的卡常过程。
1. 开 `long long` 会 MLE，直接开 `int`；
2. 数组开 $3\times 10^6$ 会 MLE，卡在上界 $2.1\times 10^6$ 刚刚好；
3. 最后的分层 BFS 同一个点会在不同层里面访问多次，但是我们不能剪掉后来的因为后来的有可能字典序更小。所以我们只需要处理同层的，每一层每个点只能访问一次，这样子就可以保证入队次数不太多，剩下的就是玄学了。
时间复杂度 $\mathcal O(能过)$。赛后 AC 代码。
```cpp
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;
const int kMaxN = 3e6 + 5;
int f[kMaxN], d[kMaxN], vis[kMaxN], n, m, cnt;
string w, ans;
vector<pair<int, char>> e[kMaxN];
vector<int> q, nxt;
vector<int> g[kMaxN];
pair<int, char> p[kMaxN];
void cover(int x) {
if (f[x]) {
return;
}
f[x] = 1;
for (int i : g[x]) {
cover(i);
}
}
void bfs(int x) {
queue<int> q;
fill(d + 1, d + cnt + 1, 1e9);
for (q.push(x), d[x] = 0; q.size(); q.pop()) {
int t = q.front();
for (int i : g[t]) {
if (d[t] + 1 < d[i]) {
d[i] = d[t] + 1;
q.push(i);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
cnt = n;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v >> w;
if (w.size() == 1) {
e[u].emplace_back(v, w[0]);
g[v].emplace_back(u);
continue;
}
e[u].emplace_back(++cnt, w.front());
g[cnt].emplace_back(u);
for (int i = 1; i < w.size() - 1; i++) {
e[cnt].emplace_back(cnt + 1, w[i]);
g[cnt + 1].emplace_back(cnt);
cnt++;
}
e[cnt].emplace_back(v, w.back());
g[v].emplace_back(cnt);
}
cover(n);
bfs(n);
for (q.emplace_back(1); q.size(); ) {
nxt.clear();
int dis = 1e9;
char c = 'z';
for (int i : q) {
for (auto j : e[i]) {
if (d[j.first] < dis) {
dis = d[j.first];
c = j.second;
} else if (d[j.first] == dis) {
c = min(c, j.second);
}
}
}
for (int i : q) {
for (auto j : e[i]) {
if (d[j.first] == dis && j.second == c && !vis[j.first]) {
nxt.emplace_back(j.first);
p[j.first] = {i, j.second};
vis[j.first] = 1;
}
}
}
for (int i : nxt) {
vis[i] = 0;
}
if (p[n].first) {
break;
}
swap(q, nxt);
}
for (int x = n; x != 1; x = p[x].first) {
ans += p[x].second;
}
reverse(ans.begin(), ans.end());
cout << ans << ' ';
ans.clear();
q.clear();
fill(p + 1, p + cnt + 1, pair<int, char>(0, 0));
for (q.emplace_back(1); q.size(); ) {
nxt.clear();
char c = 'z';
for (int i : q) {
for (auto j : e[i]) {
if (f[j.first] && j.second < c) {
c = j.second;
}
}
}
for (int i : q) {
for (auto j : e[i]) {
if (f[j.first] && j.second == c && !vis[j.first]) {
nxt.emplace_back(j.first);
p[j.first] = {i, j.second};
vis[j.first] = 1;
}
}
}
for (int i : nxt) {
vis[i] = 0;
}
if (p[n].first) {
break;
}
swap(q, nxt);
}
for (int x = n; x != 1; x = p[x].first) {
ans += p[x].second;
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
return 0;
}
```
## 日记和欧拉函数
首先我一眼就看见了 $\le 10^6$，因此我先使用线性筛 $\mathcal O(n)$ 求出所有欧拉函数的值。然后就是求 $\varphi^x(i)$。这个有点类似于 LCA 的倍增上跳，因此我们直接 $\mathcal O(n\log_2 n)$ 预处理倍增加 $\mathcal O(\log_2 n)$ 单次查询即可。（不过赛后发现暴力跳最多跳 $2\left\lceil\log_2 x\right\rceil$）
于是我们就可以预处理出 $S(n)=\sum\limits_{i=1}^n \varphi^{\left(\max\limits_{j=1}^i \varphi(j)-B\right)}(i)$，最后 $S(r)-S(l)$ 就是答案了。
- [p] 最后再加上 $B=10^9$ 的 $f(i)=i$ 和 $B=0$ 的 $f(i)=1$，成功获得 $80$ 分。
现在就是进阶操作了。首先这个求和式子及其的不规则，所以是很难搞出来的。所以需要进行找规律。对于 $i\le B$，由于 $\varphi(i)\le i$，所以有 $\varphi(i)\le B$，也就是 $\max\limits_{j=1}^i \varphi(j)-B\le 0$，所以对于 $i\le B$ 有 $f(i)=i$。
然后打标观察，在 $B$ 往后大约 $400$ 个数都是无规律的，但是 $400$ 个之后就都变成 $1$ 了。证明不太会，大概就是大于一个值了之后 $\max\limits_{j=1}^i \varphi(j)-B$ 就会大于等于 $60$，此时就一定会跳成 $1$。
可以找一个大于 ${} B+60 {}$ 的质数 $p$，那么有 $\varphi(p)=p-1$ 也就有 $\varphi(p)-B\ge 60$ 即 $\max\limits_{j=1}^p \varphi(j)-B\ge 60$，往后这个数一定会更大所以最终都会变成 $1$。而设置 $400$ 的原因是这个数大小刚刚好，其实也可以直接暴力找大于 $B+60$ 的第一个质数作为分界点。
而对于 $B\le i\le B+400$，直接暴力求解欧拉函数即可。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
LL sum[401], t, b;
bool isPrime(LL x) {
if (x <= 1) {
return 0;
}
for (LL i = 2; i * i <= x; i++) {
if (x % i == 0) {
return 0;
}
}
return 1;
}
LL max(LL x) {
for (LL i = x; i; i--) {
if (isPrime(i)) {
return i;
}
}
return 2;
}
LL phi(LL x) {
if (x == 1) {
return 1;
}
LL ans = x;
for (LL i = 2; i * i <= x; i++) {
if (x % i == 0) {
ans = ans / i * (i - 1);
for (; x % i == 0; x /= i) { }
}
}
if (x > 1) {
ans = ans / x * (x - 1);
}
return ans;
}
LL calc(LL x, LL y) {
if (y <= 0) {
return x;
}
while (y--) {
if (x == 1) {
break;
}
x = phi(x);
}
return x;
}
LL solve(LL x) {
if (x <= b) {
return x * (x + 1) / 2;
} else {
return sum[min(400LL, x - b)] + (x > b + 400) * (x - b - 400);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> t >> b;
sum[0] = b * (b + 1) / 2;
for (LL i = 1; i <= 400; i++) {
sum[i] = sum[i - 1] + calc(b + i, max(b + i) - b - 1);
}
for (LL l, r; t; t--) {
cin >> l >> r;
cout << solve(r) - solve(l - 1) << '\n';
}
return 0;
}
```
## 日记和二叉搜索树
首先枚举任意一个数作为 LCA，那么所有的 $(u,v)$ 一定满足 $u$ 和 $v$ 在 LCA 的不同儿子的子树里。然后稍微推一下式子就可以得到 LCA 的值一定是介于两个子树的值域之间的，因为在子树值域中间不忧（可以推式子，最后会变成一个一次函数，不要像我一样考场上推错了）。
而子树大小之和是给定的，把子树大小分成两部分最大化乘积，可以做背包，找到离和 $/2$ 最近的方案。具体实现需要卡常。
```cpp
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;
const int kMaxN = 1e6 + 5;
int siz[kMaxN], fa[kMaxN], n;
long long ans;
vector<int> e[kMaxN], v, t;
void dfs(int x, int f) {
siz[x] = 1;
fa[x] = f;
for (int i : e[x]) {
if (i != f) {
dfs(i, x);
siz[x] += siz[i];
}
}
}
template <size_t mx>
void solve(const vector<int> &v, int sum) {
if (mx < size_t(sum / 2 + 1)) {
solve<min(2 * mx, (size_t)5e5)>(v, sum);
return;
}
bitset<mx + 5> dp;
dp.set(mx);
for (int i : v) {
dp |= dp >> i;
}
int p = dp._Find_next(mx - sum / 2 - 1);
ans += 1LL * (mx - p) * (sum - (mx - p));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
int sum = 0, mx = 0;
v.clear(), t.clear();
for (int j : e[i]) {
if (j != fa[i]) {
v.emplace_back(siz[j]);
mx = max(mx, siz[j]);
sum += siz[j];
}
}
if (v.size() <= 1) {
continue;
}
if (v.size() == 2) {
ans += 1LL * v[0] * v[1];
continue;
}
if (v.size() == 3) {
ans += max(1LL * v[0] * (v[1] + v[2]), max(1LL * v[1] * (v[0] + v[2]), 1LL * v[2] * (v[0] + v[1])));
continue;
}
if (mx >= sum / 2) {
ans += 1LL * mx * (sum - mx);
continue;
}
sort(v.begin(), v.end());
v.emplace_back(-1);
int cnt = 1;
for (int i = 1; i < v.size(); i++) {
if (v[i] != v[i - 1]) {
int x = v[i - 1], j = 1;
for (; j < cnt; j *= 2) {
t.emplace_back(x * j);
cnt -= j;
}
t.emplace_back(x * cnt);
cnt = 1;
} else {
cnt++;
}
}
solve<8>(t, sum);
}
cout << ans << '\n';
return 0;
}
```
## 日记和编辑器
直接写的 STL 暴力。成功获得 $64$ 分。