题目大意：给一棵基环树，两种操作：
- $1\;x\;y：$把第$x$条边长度改成$y$
- $2\;x\;y：$查询$x$到$y$的最短距离
题解：发现最短距离只有两种可能，第一个是树上的距离，第二种是经过多出来的一条边，都求出来比较一下就行了。修改时，若修改的是多出来的边，直接修改即可，若不是可以把它子树中所有点的距离修改，可以按$dfs$序变成区间修改
卡点：无
C++ Code：
#include#include #define maxn 100010int head[maxn], cnt = 1;struct Edge { int to, nxt, w;} e[maxn << 1];inline void add(int a, int b, int c) { e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b], c}; head[b] = cnt;}int n, m, circle;int l[maxn], r[maxn], w[maxn];#define M 17int fa[maxn][M], dep[maxn], sz[maxn];int dfn[maxn], idx;bool vis[maxn];void dfs(int u, int father = 0) { for (int i = 1; i < M; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1]; vis[u] = true; dfn[u] = ++idx; sz[u] = 1; for (int i = head[u]; i; i = e[i].nxt) if (i ^ father ^ 1) { int v = e[i].to; if (!vis[v]) { *fa[v] = u; dep[v] = dep[u] + 1; dfs(v, i); sz[u] += sz[v]; } else circle = i >> 1; }}inline int LCA(int x, int y) { if (x == y) return x; if (dep[x] < dep[y]) std::swap(x, y); for (int i = dep[x] - dep[y]; i; i &= i - 1) x = fa[x][__builtin_ctz(i)]; if (x == y) return x; for (int i = M - 1; ~i; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return *fa[x];}#undef Mint last[maxn];namespace BIT { long long Tr[maxn], res; inline void add(int p, int num) {for (; p <= n; p += p & -p) Tr[p] += num;} inline int ask(int p) {for (res = 0; p; p &= p - 1) res += Tr[p]; return res;}}inline void __modify(int u, int v, int w) {BIT::add(u, w), BIT::add(v + 1, -w);}inline void modify(int u, int v, int w) { if (dfn[u] > dfn[v]) std::swap(u, v); __modify(dfn[v], dfn[v] + sz[v] - 1, w - ::last[v]); ::last[v] = w;}inline long long dis(int x, int y) {return BIT::ask(dfn[x]) + BIT::ask(dfn[y]) - BIT::ask(dfn[LCA(x, y)]) * 2;}inline long long solve(int x, int y) { long long ans = dis(x, y); ans = std::min(ans, dis(x, l[circle]) + dis(y, r[circle]) + w[circle]); return std::min(ans, dis(x, r[circle]) + dis(y, l[circle]) + w[circle]);}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d%d%d", l + i, r + i, w + i); add(l[i], r[i], w[i]); } dfs(1); for (int i = 1; i <= n; i++) if (i != circle) modify(l[i], r[i], w[i]); while (m --> 0) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if (op == 1) { if (x == circle) w[circle] = y; else modify(l[x], r[x], y); } else printf("%lld\n", solve(x, y)); } return 0;}