本题大概是一个基环树上带修改边权的最短距离。可以把他看做一棵树,把多的那条边拎出来,树剖维护距离,分类讨论即可。大概是你谷蓝题难度吧。

由于树剖只需要查询 dfs 序上区间最小值,可以考虑树状数组维护常熟较小。目前不卡常的情况下你谷效率 rk1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define getc(x) getchar(x)
#define putc(x) putchar(x)

template <typename T> inline void read(T &x) {
x = 0; register char ch; register bool fl = 0;
while (ch = getc(), ch < 48 || 57 < ch) fl ^= ch == '-'; x = (ch & 15);
while (ch = getc(), 47 < ch && ch < 58) x = (x << 1) + (x << 3) + (ch & 15);
if (fl) x = -x;
}
template <typename T> inline void readc(T &x) {
while (x = getc(), !islower(x) && !isupper(x));
}
template <typename T> inline void print(T x, char c = ' ') {
static int buf[40];
if (x == 0) { putc('0'); putc(c); return; }
if (x < 0) putc('-'), x = -x;
for (buf[0] = 0; x; x /= 10) buf[++buf[0]] = x % 10 + 48;
while (buf[0]) putc((char) buf[buf[0]--]);
putc(c);
}

const int maxn = 100010;

int n, m, x, y, u, v, w, tu, tv, tw, opt, ans, pos;
int a[maxn], s[maxn], cst[maxn], tmp[maxn];
int fa[maxn], id[maxn], top[maxn], son[maxn], wid[maxn], dep[maxn], siz[maxn];
bool vis[maxn];

int tot = 2, hed[maxn], to[maxn << 1], val[maxn << 1], nxt[maxn << 1];
struct edge {
int u, v, w;
} e[maxn];

void dfs1(int u) {
vis[u] = siz[u] = 1;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (!vis[v]) {
fa[v] = u, dep[v] = dep[u] + 1, cst[v] = val[i];
dfs1(v);
siz[u] += siz[v];
if (siz[v] > siz[son[u]])
son[u] = v;
} else if (v != fa[u]) {
tu = u, tv = v, tw = val[i];
}
}

void dfs2(int u, int toppoint) {
top[u] = toppoint, id[u] = ++pos, wid[id[u]] = u;
if (siz[u] == 1) return;
dfs2(son[u], toppoint);
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (v != fa[u] && v != son[u] && !(u == tu && v == tv) && !(u == tv && v == tu))
dfs2(v, v);
}

int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]])
std::swap(u, v);
v = fa[top[v]];
}
if (dep[u] > dep[v])
std::swap(u, v);
return u;
}

void modify(int k, int w) {
for (int i = k; i <= n; i += i & -i)
s[i] += w - tmp[k];
tmp[k] = w;
}

int query(int l, int r) {
int ret = 0;
for (int i = r; i; i -= i & -i)
ret += s[i];
for (int i = l - 1; i; i -= i & -i)
ret -= s[i];
return ret;
}

int query_path_to_root(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
ret += query(id[top[u]], id[u]);
u = fa[top[u]];
}
if (u != v)
ret += query(id[son[v]], id[u]);
return ret;
}

int query_path(int u, int v) {
int ret = 0, t = lca(u, v);
ret += query_path_to_root(u, t);
ret += query_path_to_root(v, t);
return ret;
}

int main() {

read(n), read(m);
for (int i = 1; i <= n; i++) {
read(u), read(v), read(w);
e[i] = edge{u, v, w};
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = w, hed[v] = tot++;
}
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++)
for (int j = id[i]; j <= n; j += j & -j)
s[j] += cst[i];
for (int i = 1; i <= n; i++)
tmp[id[i]] = cst[i];
for (int i = 1; i <= m; i++) {
read(opt), read(x), read(y);
if (opt == 1) {
u = e[x].u, v = e[x].v;
if ((u == tu && v == tv) || (u == tv && v == tu)) {
tw = y;
} else {
u = dep[u] > dep[v] ? u : v;
modify(id[u], y);
}
} else {
ans = query_path(x, y);
ans = std::min(ans, query_path(x, tu) + query_path(tv, y) + tw);
ans = std::min(ans, query_path(y, tu) + query_path(tv, x) + tw);
print(ans, '\n');
}
}

return 0;
}