洛谷题单指南-连通性问题-CF487E Tourists

原题链接：https://www.luogu.com.cn/problem/CF487E

题意解读：连通的无向图，每个节点有权值，支持两种操作：1、修改节点权值 2、计算一条路径上的最小点权值

解题思路：

1、问题分析

对于一个单点修改，区间查询问题，很容易想到线段树

但是由于是在路径上，因此需要用到树链剖分，有因为是无向图而不是树，需要先进行转换。

圆方树正合适，可以设方点权值为所连接圆点的最小值，圆点权值就是图中节点的权值，这样对于查询操作来说没有压力，但是对于修改操作，

如果修改圆点权值，需要修改与其连接的所有方点的点权值，这个复杂度就没法接受了。

进一步优化，在修改圆点权值时，只需要修改其父节点的权值即可，其父节点肯定是方点，另外也要通过dfs求出圆方树中的父子关系。

由于要更新圆点的父节点方点的权值，还需要保存方点所有子圆点的权值，这里可以用multiset，修改圆点时，先删除multiset中对应权值，然后插入新权值，再取最小值来更新方点的权值。

到这里，修改的问题解决了，查询应该如何处理？

在查询一条路径的最小值时，先正常采用树链剖分以及线段树求区间最小值，最后要看一下路径两端点的LCA，如果LCA是方点，则还需要看一下其

父节点的权值，综合求最小值。

这是因为：

方点记录的是所有子节点的最小值，还要看一下其父节点的圆点
路径中间的方点不需要特殊处理，因为路径上的方点的父节点也在路径上
2、算法流程

用tarjan算法，求圆方树
dfs1圆方树，计算父子关系，同时初始化树链剖分相关的数组
dfs2圆方树，计算树链剖分相关数组
执行单点修改以及路径查询操作，其中路径查询要操作要拆解到区间用线段树来执行
100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200005, M = 800005, INF = 0x3f3f3f3f;

int head1[N], head2[N], to[M], nxt[M], idx; //head1:原图 head2:圆方树
int w[N]; //圆方树的点权值，方点的权值是子圆点的最小值
multiset<int> s[N]; //方点所有子圆点的权值
int dfn1[N], low[N], timestamp1; //tarjan相关
stack<int> stk;
int cnt; //点双个数
int depth[N], fa[N], son[N], sz[N], top[N], dfn2[N], rk[N], timestamp2; //树链剖分相关
struct 
{
    int l, r;
    int minx; //l~r区间最小的权值
} tr[N * 4]; //线段树
int n, m, q;

void add(int head[], int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u, int p)
{
    dfn1[u] = low[u] = ++timestamp1;
    stk.push(u);
    for(int i = head1[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        if(!dfn1[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);

            if(low[v] >= dfn1[u])
            {
                cnt++; //点双编号
                add(head2, u, cnt + n), add(head2, cnt + n, u); //圆方树建边
                while(true)
                {
                    int t = stk.top(); stk.pop();
                    add(head2, t, cnt + n), add(head2, cnt + n, t); //圆方树建边
                    if(t == v) break;
                }
            }
        }
        else low[u] = min(low[u], dfn1[v]);
    }
}

void dfs1(int u, int p)
{
    if(u <= n && p > n) 
    {
        w[p] = min(w[p], w[u]); //方点权值是所有子节点的权值最小值
        s[p].insert(w[u]); //保存方点的所有子圆点权值
    }
    fa[u] = p;
    depth[u] = depth[p] + 1;
    sz[u] = 1;
    for(int i = head2[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int t)
{
    top[u] = t;
    dfn2[u] = ++timestamp2;
    rk[timestamp2] = u;
    if(son[u]) dfs2(son[u], t);
    for(int i = head2[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

void pushup(int u)
{
    tr[u].minx = min(tr[u << 1].minx, tr[u << 1 | 1].minx);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, INF};
    if(l == r) tr[u].minx = w[rk[l]];
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

//修改线段树pos处节点值为val
void update(int u, int pos, int val)
{
    if(tr[u].l == tr[u].r) 
    {
        tr[u].minx = val; 
        w[rk[pos]] = val; 
    }
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(pos <= mid) update(u << 1, pos, val);
        else update(u << 1 | 1, pos, val);
        pushup(u);
    }
}

//查询线段树区间L~R范围最小值
int query(int u, int L, int R)
{
    if(tr[u].l >= L && tr[u].r <= R) return tr[u].minx;
    else if(tr[u].l > R || tr[u].r < L) return INF;
    else return min(query(u << 1, L, R), query(u << 1 | 1, L, R));
}

int queryPath(int u, int v)
{
    int res = INF;
    while(top[u] != top[v])
    {
        if(depth[top[u]] < depth[top[v]]) swap(u, v);
        res = min(res, query(1, dfn2[top[u]], dfn2[u]));
        u = fa[top[u]];
    }
    if(depth[u] > depth[v]) swap(u, v);
    res = min(res, query(1, dfn2[u], dfn2[v]));
    if(u > n && fa[u]) res = min(res, w[fa[u]]); //如果lca是方点，则需要看父节点的权值
    return res;
}

int main()
{
    memset(w, 0x3f, sizeof(w));
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(head1, u, v), add(head1, v, u);
    }
    //tarjan构建圆方树
    tarjan(1, 0);

    //树链剖分初始化
    dfs1(1, 0);
    dfs2(1, 1);

    //构建线段树
    build(1, 1, n + cnt);

    while(q--)
    {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if(op == 'C') 
        {
            if(fa[a]) //如果父节点是方点
            {
                s[fa[a]].erase(s[fa[a]].lower_bound(w[a])); //删除原来的权值
                s[fa[a]].insert(b); //插入新权值
                update(1, dfn2[fa[a]], *s[fa[a]].begin()); //修改父节点-方点权值为子圆点中最小值
            }
            update(1, dfn2[a], b); //注意要先修改父节点，以防w[a]被修改
        }
        else cout << queryPath(a, b) << endl;
    }

    return 0;
}