## Happy Card
#贪心 #二分
首先看到如此恶心的 T1 大脑先未响应半小时再说。接着不难发现 **炸** 和 **三带一** 可以合并成额外带的牌没有任意限制的 **三带一**。
考虑贪心。显然尽量使用 **三带一** 是最优的，因为这种方法可以一次去掉 $4$ 张牌，就算影响到了剩余牌的奇偶性，也能视作丢掉 $3$ 张牌。
所以我们可以尝试求 $\sum\limits_{i=1}^n \left\lfloor\cfrac{a_i}{3}\right\rfloor$，即可以打出 **三带一** 的最多次数。但是打完后剩余的牌不能小于这个数，否则带不上单牌。所以考虑二分 **三带一** 的次数，在满足次数的情况下剩余牌数量不能小于 **三带一** 的次数。
```cpp
bool check(LL x) {
LL need = x, res = 0;
for (LL i = 1; i <= n; i++) {
LL add = a[i] / 3;
if (add <= need) {
need -= add;
res += a[i] % 3;
} else {
res += a[i] - need * 3;
need = 0;
}
}
if (need || x > res) {
return 0;
}
return 1;
}
```
现在我们得到了可以打出的 **三带一** 的最多次数，模拟一遍后得到打出 **三带一** 中的 **三个同样的牌** 的剩余牌。现在我们需要打出 **三带一** 对应的单牌。
另外两种出牌方式是 **单牌** 和 **对子**。对于 $x$ 张剩余的牌，它需要最少 $\left\lfloor\cfrac{x}{2}\right\rfloor$ 的次数才能打完。所以我们打完 **三带一** 所对应的单牌后，奇数的数量要尽量少。
贪心地考虑，可以先把所有奇数的牌打掉。如果还剩奇数张牌要丢，那么就只能额外加一个奇数了。所以分类讨论打的单牌能否打掉所有的奇数牌即可。
最后我们先计算出 $\sum\limits_{i=1}^n\left\lfloor\cfrac{a_i}{2}\right\rfloor$（如果最后打掉奇数的还剩下 $res$ 个需要打出，那么这个值可以减掉 $\left\lfloor\cfrac{res}{2}\right\rfloor$），而最后奇数的数量是可以计算出来的。加起来再加上最初 **三带一** 的数量即可得到答案。
> [!question] Q & A
>
> **Q**：既然我们是随便选的牌打三带一中的三张，那么有没有可能会导致剩余的牌当中奇数的数量达不到最优？
>
> **A**：把 $-3$ 从 $x$ 移到 $y$，$x$ 和 $y$ 的奇偶性会同时改变，所以剩下的奇数数量一定是一样的。
```cpp
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
LL sum = 0;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
LL tim = 0, need = 0;
for (LL l = 0, r = sum; l <= r; ) {
LL m = (l + r) / 2;
if (check(m)) {
tim = m;
l = m + 1;
} else {
r = m - 1;
}
}
for (LL i = 1; i <= n; i++) {
LL add = a[i] / 3;
if (need + add <= tim) {
need += add;
a[i] %= 3;
} else {
a[i] -= (tim - need) * 3;
need = tim;
}
}
LL cnt = 0, ans = 0;
for (LL i = 1; i <= n; i++) {
cnt += a[i] % 2;
ans += a[i] / 2;
}
if (tim < cnt) {
cout << tim + (cnt - tim) + ans << '\n'; // 减掉部分奇数的
} else {
cout << tim + ans - (tim - cnt) / 2 << '\n'; // 减掉所有奇数的，再减掉额外的（两次可以减小一次答案）
}
}
return 0;
}
```
## Speaker
#树形dp #树链剖分 #线段树 #ST表 #最近公共祖先 #前缀和 #倍增
首先我们把 $x\rightarrow z\rightarrow y$ 的路线看成在 $x\rightarrow y$ 的路径上取一个点 $p$，使得 $x\rightarrow p$ 然后从 $p$ 往返到 $z$、最后从 $p\rightarrow y$ 的路线最近。
为什么一定是这样呢？不能从 $p$ 直接走到 $y$ 而不回到 $x\rightarrow y$ 路径上吗？当然不行，这样子两点间就会有超过一种走法，不符合树的结构。
于是问题就转化成了在 $x\rightarrow y$ 的路径上取一点 $p$，使得另外任意一点 $z$ 有 $a_x+2\times d_{(p,x)}$ 最大。答案最后再加上 $d_{(x,y)}$，因为这是一定要走的部分。
整个路径上每个点的信息并很好维护，但是我们需要求出对于每个点 $i$ 的值 ${} \max\limits_{j=i}^n \left(a_j+2\times d_{(i,j)}\right) {}$ 才可以维护。
这个值可以通过树形 DP 和换根解决。首先先考虑 $j$ 在 $i$ 子树中的情况，那么对于 $f_i$（初始化为 $a_i$），枚举 $i$ 的儿子 $j$，令 $f_i\gets\max(f_i,f_j+2\times w_{(i,j)})$。
```cpp
void dfs1(LL x, LL f) {
down[x] = a[x];
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
pre[i.first] = pre[x] + i.second;
dfs1(i.first, x);
down[x] = max(down[x], down[i.first] - 2 * i.second);
}
}
```
然后考虑 $j$ 不在 $i$ 子树中的情况（为了方便规定 $j=i$ 合法），设最大值为 $g_i$。那么对于 $i$，$j$ 可以：
- 存在于它的兄弟的子树当中。遍历父亲时，对儿子的 $f$ 值做前缀后缀最大值就可以对儿子转移时查询。
- 不存在于它的父亲的子树当中，即要向上至少两层。那么可以通过父亲的 $f$ 值转移过来。
这两个 DP 时间复杂度都是 $\mathcal O(n)$ 的。
```cpp
void dfs2(LL x, LL f) {
up[x] = max(up[x], a[x]);
vector<LL> son, val, pre, suf;
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
son.push_back(i.first);
val.push_back(i.second);
pre.push_back(down[i.first] - 2 * i.second);
suf.push_back(down[i.first] - 2 * i.second);
}
for (LL i = 1; i < pre.size(); i++) {
pre[i] = max(pre[i], pre[i - 1]);
}
for (LL i = (LL)suf.size() - 2; i >= 0; i--) {
suf[i] = max(suf[i], suf[i + 1]);
}
for (LL i = 0; i < son.size(); i++) {
up[son[i]] = max(i > 0 ? pre[i - 1] : (LL)-1e18,
i < son.size() - 1 ? suf[i + 1] : (LL)-1e18) -
2 * val[i];
up[son[i]] = max(up[son[i]], up[x] - 2 * val[i]);
dfs2(son[i], x);
}
}
```
对于 $i$，$\max\left(f_i,g_i\right)$ 就是答案。
现在我们需要维护路径上的答案。首先可以想到重链剖分。由于不带修，用 ST 表维护 dfs 序所对应的序列的区间 $\max$。单次查询时间复杂度 $\mathcal O\left(\log_2 n\right)$。当然如果你大脑残废写了线段树把查询复杂度干到了 $\mathcal O\left(\log^2 n\right)$ 好像也可以过。
不过倍增也是可以的，额外维护每个节点向上跳 $2^k$ 步经过的点的最大值也是可以的。时间复杂度 $\mathcal O\left(\log_2 n\right)$。
维护 $1$ 到每个节点的路径长度，顺带求 LCA 来查询 $x\rightarrow y$ 的路程。
总时间复杂度 $\mathcal O\left(n+q\log_2 n\right)$。
```cpp
void prework1(LL x, LL f) {
fa[x] = f;
dep[x] = dep[f] + 1;
siz[x] = 1;
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
prework1(i.first, x);
siz[x] += siz[i.first];
if (siz[i.first] > siz[son[x]]) {
son[x] = i.first;
}
}
}
void prework2(LL x, LL t) {
top[x] = t;
dfn[x] = ++cnt;
if (!son[x]) {
return;
}
prework2(son[x], t);
for (auto i : e[x]) {
if (i.first == fa[x] || i.first == son[x]) {
continue;
}
prework2(i.first, i.first);
}
}
LL query(LL l, LL r) {
LL k = lg[r - l + 1];
return max(dp[l][k], dp[r - (1 << k ) + 1][k]);
}
LL solve(LL x, LL y) {
LL res = 0, len = pre[x] + pre[y];
for (; top[x] != top[y]; x = fa[top[x]]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
res = max(res, query(dfn[top[x]], dfn[x]));
}
if (dep[x] > dep[y]) {
swap(x, y);
}
res = max(res, query(dfn[x], dfn[y]));
return res - (len - 2 * pre[x]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
dfs1(1, 0);
dfs2(1, 0);
prework1(1, 0);
prework2(1, 1);
for (LL i = 1; i <= n; i++) {
dp[dfn[i]][0] = max(down[i], up[i]);
}
for (LL j = 1; j < kLog; j++) {
for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
for (LL i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (LL x, y; q; q--) {
cin >> x >> y;
cout << a[x] + a[y] + solve(x, y) << '\n';
}
return 0;
}
```
## Monotonic Queue
#序列dp #单调栈
不会，写的爆搜，甚至答案计算都是抄的题面上的。成功获得 $4$ 分。
## XA-Game
#矩阵 #快速幂
不会，暴力都没打，成功 $0$ 分。