OI笔记 | 2023.7-11 做题记录（一）
- 图
- [十二省联考 2019] 春节十二响
- 树
- 街道
- Addition and Subtraction
- Rectangle Painting 1
- [ABC139E] League
- [JSOI2007] 建筑抢修
- 字符串
- Groceries in Meteor Town
图
给你一个 $n$ 个点，$m$ 条边的无向连通有权图，将其中任意不同两点的距离从小到大排列。
求这个排列中第 $k$ 个元素的大小，也即图中第 $k$ 短的最短路。
$n\le 2\times 10^5, k\le 400$
题解
$k$ 很小，从它入手。
注意到直接选前 $k$ 短的边建新图，答案一定在新图产生，因为边权为正，如果多加了一条边，路径长度必然增加，而前 $k$ 短的边已经控制了第 $k$ 短的最短路的长度的上限，不会再增加了。
那么对于新图枚举起点做最短路即可。
时间复杂度 $O(k^2\log k)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 2e5 + 10, MAX_K = 400 + 10;
const ll INF = (1ll << 60);
int n, m, k, tot, cnt, ecnt, fir[MAX_N], id[MAX_N];
ll D[MAX_N], res[MAX_N + MAX_K];
bool vis[MAX_N], used[MAX_N];
struct Ed {
int u, v, w;
Ed(int _u = 0, int _v = 0, int _w = 0) :
u(_u), v(_v), w(_w) { }
bool operator < (const Ed &t) const { return w < t.w; }
} edges[MAX_N];
struct edge {
int v, w, nxt;
edge() { }
edge(int _v, int _w, int _nxt) :
v(_v), w(_w), nxt(_nxt) { }
} E[MAX_N];
void AddEdge(int u, int v, int w) {
E[++ecnt] = edge(v, w, fir[u]);
fir[u] = ecnt;
}
void dijkstra(int s) {
for(int i = 1; i <= tot; i++)
D[i] = INF, vis[i] = false;
D[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(make_pair(0, s));
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = fir[u]; i; i = E[i].nxt) {
int v = E[i].v, w = E[i].w;
if(D[u] + w < D[v]) {
D[v] = D[u] + w;
q.push(make_pair(D[v], v));
}
}
}
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
edges[i] = Ed(u, v, w);
}
sort(edges + 1, edges + m + 1);
for(int i = 1; i <= k; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if(!used[u]) {
used[u] = true;
id[u] = ++tot;
}
if(!used[v]) {
used[v] = true;
id[v] = ++tot;
}
AddEdge(id[u], id[v], w);
AddEdge(id[v], id[u], w);
}
for(int i = 1; i <= tot; i++) {
dijkstra(i);
for(int j = i + 1; j <= tot; j++)
res[++cnt] = D[j];
if(cnt > k) {
sort(res + 1, res + cnt + 1);
cnt = k;
}
}
write(res[k]), putchar('\n');
fclose(stdin);
fclose(stdout);
return 0;
}
[十二省联考 2019] 春节十二响
给一棵 $n$ 个点的树，每个点有一个权值 $w_i$。
你每次可以选取树上的一个点集，要求点集中的每个点不能是另一个点 的祖先，而选出点集的代价为点集中权值最大点的权值。
问将所有点都选一遍的最小代价为多少，每次选的点集不能包含之前已 经被选过的点。
$n\le 2\times 10^5$
题解
考虑若树是一条链，该怎么做。此时若树根是链的一端，则只能一个一个选。否则树根在链的中间，则只能每次从根的左右各选一个。要让代价最小，我们要贪心地把左的最大和右的最大配对。
考虑一般情况，那就和链上有点像，对于每个节点 $u$，维护一个 $u$ 的子树中可选的最优解集 $E_u$。这个集合显然可以从它的儿子节点中合并而来。只需要把子树两两合并，且每次配对后只保留两个最大值中较大的那一个进入新的最优解集，最后并上这个节点本身的权值。
但复杂度不太对，这么做最坏是 $\mathcal{O}(n^2 \log n)$。换成启发式合并就可以变成正解 $\mathcal{O}(n\log n)$ 的。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 2e5 + 10;
int n, cnt, M[MAX_N], tmp[MAX_N];
ll ans;
vector<int> G[MAX_N];
multiset<int, greater<int>> E[MAX_N];
void dfs(int u) {
for(int v : G[u]) {
dfs(v);
cnt = 0;
if(E[u].size() < E[v].size()) swap(E[u], E[v]);
while(!E[v].empty()) {
tmp[++cnt] = max(*E[u].begin(), *E[v].begin());
E[u].erase(E[u].begin());
E[v].erase(E[v].begin());
}
while(cnt) E[u].insert(tmp[cnt--]);
}
E[u].insert(M[u]);
}
int main() {
n = read();
for(int i = 1; i <= n; i++)
M[i] = read();
for(int i = 2, fa; i <= n; i++) {
fa = read();
G[fa].pb(i);
}
dfs(1);
for(int v : E[1])
ans += v;
write(ans), putchar('\n');
return 0;
}
树
我们称一棵权值为 $w$ 的树是 “好的”，当且仅当：
-
它的若干个（至少 $2$ 个）子树均为权值、结构相同的 “好的” 树，且权值和不超过 $w$。
-
称 “浪费的权值” 为 $w-$ 子树权值和，浪费的权值和 $<$ 子树个数。
特别地，一个点被视作权值为 $1$ 的 “好的” 树。
你需要求出权值为 $n$ 的，“好的” 树的形态数量。
$n \le 10^9$
题解
显然考虑 dp，我们设 $f_w$ 为权值为 $w$ 的，“好的”树的形态数量。边界情况为 $f_1=1$。则枚举它的子树的个数 $i$ 和权值大小 $k$，暴力转移如下：
\[f_w=\sum_{i=2}^w \sum_{k=1}^{w} f_k\]暴力转移同时判断状态是否满足题意，时间复杂度 $\mathcal{O}(n^3)。$
考虑题目条件的另一种表达方式：$w=i\times k+p$，其中 $p$ 为 “浪费的权值”，所以 $k< i$。
这里可以看出很像余数的表达形式。即 $p$ 为余数，$k$ 只有一种取值，为 $\lfloor \frac{w}{i}\rfloor$。所以转移方程可以重新写出：
\[f_{w}=\sum_{i=2}^w f_{\lfloor \frac{w}{i}\rfloor}\]那么这个就是整除分块能做的事了。时间复杂度直线掉到 $\mathcal{O}(n\sqrt n)$。
然后本题可以证明，如果我们只需求出 $f_n$，则有用的状态并不多，大概级别为 $\mathcal{O}(n^{\frac{3}{4}})$。所以记忆化搜索可以过本题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
int n;
unordered_map<int, ll> f;
ll dfs(int x) {
if(f[x]) return f[x];
ll res = 0;
for(int l = 2, r; l <= x; l = r + 1) {
r = min(x, x / (x / l));
res += dfs(x / l) * (r - l + 1);
}
return f[x] = res;
}
int main() {
n = read();
f[1] = 1;
write(dfs(n));
return 0;
}
街道
共 $n$ 个人有顺序地站在宽度为 $W$ 的街道上，每人有一个宽度 $w_i$。
两个相邻的人宽度之和不超过街道宽度时，他们可以交换前后位置。
你需要统计出人群有多少种站位方式。答案对 $998244353$ 取模。
$n\le 10^6$
题解
考虑比较特殊的两个人，宽度最小的人 $u$ 和宽度最大的人 $v$。分成两种情况考虑：
-
如果 $w_u + w_v\leq W$，则发现 $u$ 可以在 $1\sim n$ 上随便走。那我们可以把 $u$ 从人群中删掉，答案乘 $n$，然后继续计算。
-
如果 $w_u+w_v > W$，则发现 $v$ 完全动不了。所以不考虑 $v$ 的贡献，只需要分治计算 $v$ 左右的答案，乘起来即可。
然后发现，我们每一轮都可以至少扔掉一个人的影响。所以只会执行 $n$ 轮。每次需要找区间最小和最大，还需要考虑单点删除，所以用线段树维护即可。时间复杂度 $\mathcal{O}(n\log n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10, INF = (1 << 30), MOD = 998244353;
int n, W, w[MAX_N];
struct node {
int mx, mxpos, mn, mnpos, delnum;
node(int _mx = -INF, int _mxpos = -1, int _mn = INF, int _mnpos = -1, int _delnum = 0) :
mx(_mx), mxpos(_mxpos), mn(_mn), mnpos(_mnpos), delnum(_delnum) { }
} d[MAX_N << 2];
inline int lc(int p) { return (p << 1); }
inline int rc(int p) { return (p << 1) | 1; }
inline int mid(int s, int t) { return s + ((t - s) >> 1); }
inline node U(node L, node R) {
node ret;
ret.mx = max(L.mx, R.mx);
ret.mxpos = L.mx > R.mx ? L.mxpos : R.mxpos;
ret.mn = min(L.mn, R.mn);
ret.mnpos = L.mn < R.mn ? L.mnpos : R.mnpos;
ret.delnum = L.delnum + R.delnum;
return ret;
}
inline void pu(int p) { d[p] = U(d[lc(p)], d[rc(p)]); }
void build_tree(int s, int t, int p) {
if(s == t) {
d[p] = node(w[s], s, w[s], s, 0);
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void del(int s, int t, int pos, int p) {
if(s == t) {
d[p] = node();
d[p].delnum = 1;
return;
}
int m = mid(s, t);
if(pos <= m) del(s, m, pos, lc(p));
else del(m + 1, t, pos, rc(p));
pu(p);
}
node query(int s, int t, int l, int r, int p) {
if(l <= s && t <= r) return d[p];
int m = mid(s, t);
node ret;
if(l <= m) ret = U(ret, query(s, m, l, r, lc(p)));
if(r > m) ret = U(ret, query(m + 1, t, l, r, rc(p)));
return ret;
}
ll solve(int l, int r) {
if(l >= r) return 1;
node P = query(1, n, l, r, 1);
if(P.mnpos == -1) return 1;
if(P.mn + P.mx <= W) {
del(1, n, P.mnpos, 1);
return solve(l, r) * (r - l + 1 - P.delnum) % MOD;
}
else return solve(l, P.mxpos - 1) * solve(P.mxpos + 1, r) % MOD;
}
int main() {
n = read(), W = read();
for(int i = 1; i <= n; i++)
w[i] = read();
build_tree(1, n, 1);
write(solve(1, n));
return 0;
}
Addition and Subtraction
给你一个只包含’+’、’-‘、正整数的式子，你需要在式子中添加一些括号，使运算结果最大，输出最大的结果。
$n\leq 10^5$
题解
考虑贪心。
首先在加号后面添括号是毫无意义的。假设我们现在要在某个减号后面添括号，考虑它的最大贡献。考察一个例子：
\[a_1-a_3+a_4+a_5-a_6+a_7-a_8+a_9\]我们尝试在第一个负号后面添加括号。
\[a_1-(a_3+a_4+a_5-a_6+a_7-a_8+a_9)\]这样添加，看来 $a_3,a_4,a_5$ 的贡献只能为负了。但是对于后面的数，我们这样添加括号：
\[a_1-(a_3+a_4+a_5-(a_6+a_7)-(a_8+a_9))\]所以括号里的第一个负号后面的贡献都能为正。容易发现，这是在第一个负号后添加括号，能得到的最好结果。
那么枚举在第几个负号后面添加减号即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll ret = 0, w = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') w = -1; c = getchar(); }
while(isdigit(c)) { ret = (ret << 1) + (ret << 3) + (c ^ 48); c = getchar(); }
return ret * w;
}
inline int readc() {
char c = getchar();
while(c != '+' && c != '-') c = getchar();
return c == '+' ? 1 : -1;
}
char buf[50];
inline void write(ll x) {
if(x < 0) x = -x, putchar('-');
int tp = 0;
do { buf[++tp] = x % 10 + 48; x /= 10; } while(x);
while(tp) putchar(buf[tp--]);
}
const int MAX_N = 1e6 + 10;
int n, cnt, sub[MAX_N];
ll ans, sum1[MAX_N], sum2[MAX_N];
int main() {
n = read();
for(int i = 1, w = 1, x; i <= n; i++) {
if(i > 1) w = readc();
x = read();
if(w == -1) sub[++cnt] = i;
sum1[i] = sum1[i - 1] + w * x;
sum2[i] = sum2[i - 1] + x;
}
ans = sum1[n];
for(int i = 1; i < cnt; i++) {
ll A = sum1[sub[i] - 1];
ll B = sum2[sub[i + 1] - 1] - sum2[sub[i] - 1];
ll C = sum2[n] - sum2[sub[i + 1] - 1];
ans = max(ans, A - B + C);
}
write(ans);
return 0;
}
Rectangle Painting 1
给定一个 $n\times n$ 的黑白矩阵，请用价值和最少的一些矩形覆盖所有黑格。
一个矩形的价值是长与宽的最大值。
$1\le n\le 50$
题解
二维区间 dp。设计状态 $dp_{x,y,X,Y}$ 表示以 $(x,y)$ 为左上角，$(X,Y)$ 为右下角的矩形的答案。
则枚举“断线”，把矩形切成上下/左右两个小矩形，合并答案即可。
具体实现可以记忆化搜索。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline bool readc() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 55;
int n, dp[MAX_N][MAX_N][MAX_N][MAX_N];
int dfs(int x, int y, int X, int Y) {
if(dp[x][y][X][Y] != -1) return dp[x][y][X][Y];
int res = max(X - x + 1, Y - y + 1);
for(int k = x; k < X; k++)
res = min(res, dfs(x, y, k, Y) + dfs(k + 1, y, X, Y));
for(int k = y; k < Y; k++)
res = min(res, dfs(x, y, X, k) + dfs(x, k + 1, X, Y));
return dp[x][y][X][Y] = res;
}
int main() {
n = read();
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dp[i][j][i][j] = readc();
write(dfs(1, 1, n, n)), putchar('\n');
return 0;
}
[ABC139E] League
$n$ 个人，每两个人之间都有一场比赛，故共 $\frac {n(n -1)} {2}$ 场比赛。
每个人都有自己想要的比赛顺序。例如 $x$ 要求按顺序与 $a_{x,1},a_{x,2},\cdots a_{x,n-1}$ 比赛。而且每个人每天只可以比一场比赛。
问最少比赛的天数为多少。若无解，输出 $-1$ 。
$n \leq 1000$
题解
因为每个人都只能取当前的对手进行比赛，所以要让每一天都减少至少一场比赛，我们必须让每一天能安排的比赛都安排上。
所以暴力枚举每一天，考察每个元素是否满足比赛条件，即当前其对手的对手是自己。时间复杂度 $\mathcal{O}(n^3)$ 。
考虑优化。我们枚举到第 $i$ 天时，不需要枚举所有元素。这是因为考虑第 $i-1$ 天已经把能安排的比赛全安排完了，那现在能安排的比赛，必然要从前一天安排过的人中产生，因为只有他们的当前对手更新了。
这样，设每一轮安排了 $p$ 场比赛，则共有 $\mathcal{O}(\frac{n^2}{p})$ 轮。每一场的枚举也只有 $\mathcal{O}(p)$ 的复杂度。则时间复杂度为 $\mathcal{O}(n^2)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1005;
int n, cnt, cntt, a[MAX_N][MAX_N], lst[MAX_N], p[MAX_N];
bool ban[MAX_N];
int main() {
n = read();
for(int i = 1; i <= n; i++) {
a[i][0] = 1;
for(int j = 1; j <= n - 1; j++)
a[i][j] = read();
p[++cntt] = i;
}
for(int k = 1; k <= n * (n - 1) / 2; k++) {
cnt = 0;
bool flag = false;
for(int c = 1; c <= cntt; c++)
ban[p[c]] = false;
for(int c = 1; c <= cntt; c++) {
int i = p[c];
int aim = a[i][a[i][0]];
if(a[i][0] >= n || a[aim][0] >= n || ban[i] || ban[aim]) continue;
if(a[aim][a[aim][0]] == i) {
a[aim][0]++;
a[i][0]++;
lst[++cnt] = i;
lst[++cnt] = aim;
ban[i] = ban[aim] = flag = true;
}
}
cntt = cnt;
for(int c = 1; c <= cnt; c++)
p[c] = lst[c];
if(!flag) {
for(int i = 1; i <= n; i++)
if(a[i][0] != n) {
write(-1), putchar('\n');
return 0;
}
write(k - 1), putchar('\n');
return 0;
}
}
write(n * (n - 1) / 2), putchar('\n');
return 0;
}
[JSOI2007] 建筑抢修
$N$ 个任务，每个任务有耗时 $T_1$ 和截止时间 $T_2$。同时最多只能做一个任务。求最多能安排几个任务。
$1 \le N < 150000$，$1 \le T_1 < T_2 < 2^{31}$。
题解
反悔贪心。
我们按截止时间将任务排序，逐渐加入答案。如果当前任务直接接着当前的答案做可以完成，则直接加进去。否则，从答案中找到耗时最长的任务，比较一下它的耗时与当前任务的耗时。如果当前任务耗时更短，则用当前任务替换耗时最长的任务，这样一定更优，因为给之后的任务留了更多时间。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 150000;
int n;
ll lt;
struct task {
int time, ddl;
} a[MAX_N];
priority_queue<int> pq;
int main() {
n = read();
for(int i = 1; i <= n; i++)
a[i].time = read(), a[i].ddl = read();
sort(a + 1, a + n + 1, [](task lhs, task rhs) { return lhs.ddl < rhs.ddl; });
for(int i = 1; i <= n; i++) {
if(a[i].time + lt <= a[i].ddl) {
pq.push(a[i].time);
lt += a[i].time;
}
else if(a[i].time < pq.top()) {
lt -= pq.top();
pq.pop();
lt += a[i].time;
pq.push(a[i].time);
}
}
write(pq.size());
putchar('\n');
return 0;
}
字符串
给定两个由小写字母组成的字符串 $s,t$，你可以对 $s$ 进行以下四种操作：
-
在任意位置添加任意一个字母，代价为 $a$。
-
删除任意一个字母，代价为 $b$。
-
替换任意一个字母，代价为 $c$。
-
交换相邻两个字母，代价为 $d$。
你需要求出将 $s$ 变为 $t$ 的最小代价。
| $ | s | , | t | \leq 4000 ,0 < a,b,c,d\leq 10000，a+b \leq 2d$ |
题解
首先对于前三个操作，就是经典的编辑距离问题，可以用类似 LCS 的 $\mathcal{O}(n^2)$ 的字符串 dp 解决。即设计状态 $f(i,j)$ 表示 $s_{1\cdots i}$ 变为 $t_{1\cdots j}$ 的最小代价，显然有如下几种情况：
-
添加一个字母 $t_j$，则 $f(i,j)=f(i - 1,j) + b$。
-
删除一个字母 $s_i$，则 $f(i,j)=f(i,j - 1) + a$。
-
把 $s_i$ 替换成 $t_j$，则 $f(i,j) = f(i-1,j-1)+c\times [s_i\neq t_j]$。
考虑操作 $4$，我们发现「删除一次并添加一次」可以等效代替「交换两个字母」，并且数据范围中限制了 $a+b\leq 2d$，那么这告诉我们，交换操作多于一次是不优的。
我们还能推出，「交换后替换」是不优的。因为这也可以被「删除一次并添加一次」等效代替。
所以有这个限制，转移就变得简单很多了。我们找到 $s$ 中前一个 $t_j$ 的位置 $k$ 和 $t$ 中前一个 $s_i$ 的位置 $l$，则有这样一个转移：
\[f(i,j) = f(k-1,l-1) + d+ (i-k-1)\times b + (j-l-1)\times a\]预处理一下 $k$ 和 $l$ 即可。时间复杂度 $\mathcal{O}(n^2)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll ret = 0, w = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') w = -1; c = getchar(); }
while(isdigit(c)) { ret = (ret << 1) + (ret << 3) + (c ^ 48); c = getchar(); }
return ret * w;
}
char buf[50];
inline void write(ll x) {
if(x < 0) x = -x, putchar('-');
int tp = 0;
do { buf[++tp] = x % 10 + 48; x /= 10; } while(x) ;
while(tp) putchar(buf[tp--]);
}
const int MAX_N = 4000;
ll dp[MAX_N][MAX_N];
int a, b, c, d, lst[27], K[MAX_N][27], L[MAX_N][27];
char s[MAX_N], t[MAX_N];
int main() {
memset(dp, 127, sizeof(dp));
a = read(), b = read(), c = read(), d = read();
scanf("%s%s", s + 1, t + 1);
int n = strlen(s + 1), m = strlen(t + 1);
for(int i = 1; i <= n; i++) {
dp[i][0] = i * b;
for(int p = 0; p < 27; p++)
K[i][p] = lst[p];
lst[s[i] - 'a'] = i;
}
for(int i = 0; i < 27; i++)
lst[i] = 0;
for(int j = 1; j <= m; j++) {
dp[0][j] = j * a;
for(int p = 0; p < 27; p++)
L[j][p] = lst[p];
lst[t[j] - 'a'] = j;
}
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(s[i] == t[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
dp[i][j] = min(dp[i][j], dp[i][j - 1] + a);
dp[i][j] = min(dp[i][j], dp[i - 1][j] + b);
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + c);
int k = K[i][t[j] - 'a'], l = L[j][s[i] - 'a'];
if(!k || !l) continue;
dp[i][j] = min(dp[i][j], dp[k - 1][l - 1] + d + (i - k - 1) * b + (j - l - 1) * a);
}
write(dp[n][m]), putchar('\n');
return 0;
}
Groceries in Meteor Town
给定 $n$ 个点的树，起初每个节点都是黑色，有 $q$ 次操作，操作共三种：
-
把下标为 $[l,r]$ 的点染成白色；
-
把下标为 $[l,r]$ 的点染成黑色；
-
询问从节点 $x$ 出发到达任意一个白色节点的简单路径上经过的边，最大可能的权值。不存在则输出 $-1$.
$n,q \leq 3\times 10^5$
题解
询问操作其实就是询问树上的瓶颈路，这个我们可以用 kruskal 重构树来做，所以 $x$ 到所有白色节点的路径上最大值就是 kruskal 重构树上 $x$ 与所有白色节点的 LCA 的权值。
然后考虑一个套路：树上一个点集的 LCA 为其中 dfs 序最大的点和 dfs 序最小的点的 LCA。所以我们用线段树维护一下白色节点中 dfs 序的最大值和最小值即可。
注意区间推平操作，我们可以维护两组最值。一个是不考虑黑白的，维护区间所有节点 dfs 序的最值 $A$；另一个是考虑黑白的，维护区间白色节点 dfs 序的最值 $V$。这样区间操作我们只需要 $V\gets A$ 或 $V\gets (\inf, -\inf)$即可。
接下来套一个倍增 LCA 就做完了。时间复杂度 $\mathcal{O}(n\log n)$。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
char buf[50];
void write(ll x) {...}
const int MAX_N = 6e5 + 10, MAX_LOG = 20, INF = (1 << 30);
const pii ORI = make_pair(INF, -INF);
int n, q, tot, dfncnt, log_2[MAX_N], id[MAX_N], dfn[MAX_N], val[MAX_N], fa[MAX_N][MAX_LOG], dep[MAX_N];
vector<int> K[MAX_N];
struct edge {
int u, v, w;
edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) { }
bool operator < (const edge &t) const { return w < t.w; }
} E[MAX_N];
struct dsu {
int fa[MAX_N];
dsu(int n) { for(int i = 1; i <= n; i++) fa[i] = i; }
inline int find(int x) { return (x == fa[x] ? x : fa[x] = find(fa[x]));}
};
struct node {
pii V, A;
int tag;
node(pii _V = ORI, pii _A = ORI, int _tag = -1) :
V(_V), A(_A), tag(_tag) { }
} d[MAX_N << 2];
void kruskal() {
sort(E + 1, E + n);
dsu D = dsu(n << 1);
int ecnt = 0;
tot = n;
for(int i = 1; i <= n - 1; i++) {
int u = E[i].u, v = E[i].v, w = E[i].w;
int fu = D.find(u), fv = D.find(v);
if(fu == fv) continue;
int now = ++tot;
val[now] = w;
K[now].pb(fu), K[now].pb(fv);
D.fa[fu] = D.fa[fv] = now;
if(++ecnt == n - 1) return;
}
}
void dfsk(int u, int pre) {
dfn[u] = ++dfncnt, id[dfncnt] = u;
fa[u][0] = pre, dep[u] = dep[pre] + 1;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : K[u])
dfsk(v, u);
}
void init_log2() {
log_2[1] = 0;
for(int i = 1; i <= (n << 1); i++)
log_2[i] = log_2[i >> 1] + 1;
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = log_2[dep[x]]; i >= 0; i--)
if(fa[x][i] && dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return x;
for(int i = log_2[dep[x]]; i >= 0; i--)
if(fa[x][i] && fa[y][i] && fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline int lc(int p) { return (p << 1); }
inline int rc(int p) { return (p << 1) | 1; }
inline int mid(int s, int t) { return s + ((t - s) >> 1); }
inline pii U(pii x, pii y) { return make_pair(min(x.first, y.first), max(x.second, y.second)); }
inline node change(node now, int type) {
if(type == 1) now.V = now.A;
if(type == 2) now.V = ORI;
now.tag = type;
return now;
}
inline void pd(int p) {
if(d[p].tag != -1) {
d[lc(p)] = change(d[lc(p)], d[p].tag);
d[rc(p)] = change(d[rc(p)], d[p].tag);
d[p].tag = -1;
}
}
void build_tree(int s, int t, int p) {
if(s == t) { d[p].A = make_pair(dfn[s], dfn[s]); return; }
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
d[p].A = U(d[lc(p)].A, d[rc(p)].A);
}
void update(int l, int r, int s, int t, int p, int type) {
if(l <= s && t <= r) { d[p] = change(d[p], type); return; }
pd(p);
int m = mid(s, t);
if(l <= m) update(l, r, s, m, lc(p), type);
if(r > m) update(l, r, m + 1, t, rc(p), type);
d[p].V = U(d[lc(p)].V, d[rc(p)].V);
}
int main() {
n = read(), q = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read(), w = read();
E[i] = edge(u, v, w);
}
kruskal();
dfsk(tot, 0);
build_tree(1, n, 1);
init_log2();
while(q--) {
int t = read();
if(t < 3) {
int l = read(), r = read();
update(l, r, 1, n, 1, t);
}
else {
int x = read();
pii T = U(d[1].V, make_pair(dfn[x], dfn[x]));
if(T.first == INF || (T.first == T.second && T.first == dfn[x])) write(-1);
else write(val[lca(id[T.first], id[T.second])]);
putchar('\n');
}
}
return 0;
}
♥