【题解】LuoGu4949：最短距离

原题传送门
基环树，不是特别的复杂
如果先把一条多余的边拿掉，然后对于每个询问

• 最短路径不经过多余边，直接树上求两点间距离
• 最短路径经过多余边，树上求多余边两端点分别到两个询问点的距离，加上多余边长度

两种情况比大小即可
至于如何求得树上两点间距离，因为有修改操作无法直接倍增解决
所以用上树剖，然后距离可以用常数更小的树状数组维护一下
注意这里用以点代边，细节处理需注意

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
struct Line{
	int x, y, z;
}line[maxn << 1];
int num, head[maxn], size[maxn], son[maxn], fa[maxn], d[maxn], val[maxn], id[maxn], top[maxn];
int Index, U, V, Len, n, m, tree[maxn];
inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
} 

void addedge(int x, int y, int z){ edge[++num] = (Edge) {y, head[x], z}; head[x] = num; }

void dfs(int u){
	size[u] = 1, son[u] = -1;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (!size[v]){
			fa[v] = u, d[v] = d[u] + 1, val[v] = edge[i].len;
			dfs(v);
			size[u] += size[v];
			if (son[u] == -1 || son[u] != -1 && size[son[u]] < size[v]) son[u] = v;	
		} else
		if (v != fa[u]) U = u, V = v, Len = edge[i].len;
	}
}

void dfs(int u, int x){
	top[u] = x, id[u] = ++Index;
	if (son[u] == -1) return;
	dfs(son[u], x);
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != son[u] && v != fa[u] && !(u == U && v == V) && !(u == V && v == U)) dfs(v, v);
	}
}

void add(int x, int y){ for (; x <= n; x += x & -x) tree[x] += y; }
int query(int x){ int sum = 0; for (; x; x -= x & -x) sum += tree[x]; return sum; }

int qrylen(int u, int v){
	int sum = 0;
	while (top[u] != top[v]){
		if (d[top[u]] < d[top[v]]) swap(u, v);
		sum += query(id[u]) - query(id[top[u]] - 1);
		u = fa[top[u]];
	}
	if (u == v) return sum;
	if (d[u] < d[v]) swap(u, v);
	return sum + query(id[u]) - query(id[v]);
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i){
		line[i] = (Line){read(), read(), read()};
		addedge(line[i].x, line[i].y, line[i].z);
		addedge(line[i].y, line[i].x, line[i].z);
	}
	dfs(1); dfs(1, 1);
	for (int i = 1; i <= n; ++i) add(id[i], val[i]);
	while (m--){
		int opt = read(), x = read(), y = read();
		if (opt == 1){
			int u = line[x].x, v = line[x].y;
			if (u == U && v == V || u == V && v == U) Len = y; else{
				if (d[u] < d[v]) swap(u, v);
				add(id[u], y - line[x].z);
				line[x].z = y;
			}
		} else{
			int sum = qrylen(x, y),
				sum1 = qrylen(x, U) + qrylen(y, V) + Len,
				sum2 = qrylen(x, V) + qrylen(y, U) + Len;
			printf("%d\n", min(sum, min(sum1, sum2)));
		}
	}
	return 0;
}