洛谷P4949 最短距离

洛谷P4949 最短距离

给出一个 n 个点 n 条边的无向连通图。
你需要支持两种操作：
修改 第 x 条边的长度为 y ；
查询 点 x 到点 y 的最短距离。
共有 m 次操作。
思路
n个点n条边的无向连通图（简单图），如果少一条边就是形成一棵树，就是一道LCA题，这题多了一条边，就要用相应的方法处理这条边。
考虑剔除的边是(uu,vv)，权值为w，那么 (u,v) 的最短距离就是 min(dis(u,v),dis(u,uu)+dis(v,vv)+w,dis(u,vv)+dis(v,uu)+w)。
dis(u, v)=dis(root, u) + dis(root, v) - 2 * dis(root, LCA(u, v))。
所以就是维护一个dis值。
考虑到对一条边修改，就会修改这条边下方所有的dis的权值，所以是区间更新；查询是单点查询。所以用树状数组维护。
又因为是树形结构，所以用树链剖分将之转换为线性结构。思路很简单，重要是代码实现。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
ll sum[maxn];
int n, m;
int head[maxn], to[maxn<<1], nex[maxn<<1], tot = 2, edge[maxn<<1], hid;
struct node {
    int x, y, z, id;
}e[maxn];//给每一条边编号
void add(int x, int y, int C) {
    to[tot] = y;
    edge[tot] = C;
    nex[tot] = head[x];
    head[x] = tot++;
}
int lowbit(int i) {return i&(-i);}
void update(int x, int C)
{
    for (int i = x; i <= n; i += lowbit(i)) {
        sum[i] += C;
    }
}
void update_(int x, int y, int C) {
    update(x, C); update(y + 1, -C);
}
ll getsum(int x) {
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += sum[i];
    return ans;
}
int dfn[maxn], siz[maxn], dep[maxn], son[maxn], cnt, fa[maxn], top[maxn];
ll dis[maxn];
bool vis[maxn];
void dfs1(int x, int f) {
    fa[x] = f;
    dfn[x] = ++cnt;
    dep[x] = dep[f] + 1;
    siz[x] = 1;
    for (int i = head[x]; ~i; i = nex[i]) {
        int v = to[i];
        if(v != f) {
            if(vis[v]) {hid = i >> 1; continue;}//hid是剔除的边
            vis[v] = true;
            e[i>>1].id = i;//给边编号，因为是链式前向星存图，i/2就是该边的编号
            dis[v] = dis[x] + edge[i];//dis记录改点到根的距离
            dfs1(v, x);
            siz[x] += siz[v];
            if(siz[v] > siz[son[x]]) son[x] = v;
        }
    }
}
void dfs2(int x, int fir) {
    top[x] = fir;
    if(son[x]) dfs2(son[x], fir);
    for (int i = head[x]; ~i; i = nex[i]) {
        int v = to[i];
        if(v == fa[x] || v == son[x] || v == e[hid].x && x == e[hid].y || v == e[hid].y && x == e[hid].x) continue;//剔除的边不参与树链剖分
        dfs2(v, v);
    }
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}
ll cal(int u, int v) {
    return getsum(dfn[u]) + getsum(dfn[v]) - 2 * getsum(dfn[LCA(u, v)]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z); add(y, x, z);
        e[i] = (node){x, y, z, 0};
    }
    vis[1] = true;
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= n; i++) update_(dfn[i], dfn[i], dis[i]);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1) {
            if(x == hid) {
                e[hid].z = y;
                continue;
            }
            int dy = y - e[x].z;//这里又是一个转换思想，修改权值等于增加差值
            e[x].z = y;
            update_(dfn[to[e[x].id]], dfn[to[e[x].id]] + siz[to[e[x].id]] - 1, dy);//区间修改要用差分思想，更新区间是该点和它的子树
        }
        else {
            cout << min(cal(x, y), min(cal(x, e[hid].x) + cal(y, e[hid].y), cal(x, e[hid].y) + cal(y, e[hid].x)) + e[hid].z) << '\n';
        }
    }
}