思路

题意是给一个数组和若干条可以交换位置的关系，要求最大化交错和 $nums[1]-nums[2]+nums[3]-\cdots$（下标从 1 开始，奇下标取正号、偶下标取负号）。

第一步：连通块内可以任意重排。 把可交换的关系看成无向图。若两个位置在同一连通块中，取连接它们的一棵生成树，沿着树边依次交换，就能把任意一个值搬到块内任意位置；不同连通块之间互不影响，可以独立安排。

第二步：块内最优安排。 用并查集把每个连通块缩成一个集合，统计块内奇下标个数 $cnt_{odd}$、偶下标个数 $cnt_{even}$。该块的贡献是

要让这个值最大，把块内所有值从大到小排序：最大的 $cnt_{odd}$ 个放到奇下标上取正号，剩下的 $cnt_{even}$ 个放到偶下标上取负号（让最小的那些去当负数显然最优）。于是该块贡献为

答案就是所有连通块贡献之和。

实现： 用并查集合并关系后，遍历 $i=1\dots n$，把 $a_i$ 归到 $i$ 所在根对应的结构体里，同时累加该根下奇、偶下标的个数；再对每个块的数组降序排序，前 $cnt_{odd}$ 个加、其余减。

注意： 答案绝对值可达 $n\cdot10^9=10^{15}$，需要用 64 位整数（代码用 #define int long long）。

复杂度： 并查集 $O((n+m)\alpha(n))$，各块排序总和 $O(n\log n)$，空间 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

//并查集模板
struct DSU{
    vector<int> p, sz;
    int comps;

    DSU(int n){
        p.assign(n+1, 0);
        iota(all(p), 0);             // 每个点初始自成一块
        sz.assign(n+1, 1);
        comps = n;
    }

    // 路径压缩查找
    int find(int x){
        return p[x]==x ? x : p[x]=find(p[x]);
    }

    // 按大小合并，返回是否真的合并了两棵不同的树
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        comps--;
        return true;
    }

    bool same(int a, int b){
        return find(a) == find(b);
    }

    int size(int x){
        return sz[find(x)];
    }

    int components() const {
        return comps;
    }

    int parent(int x) const {
        return p[x];
    }
};

// 每个连通块的统计信息
struct node{
    int eve = 0;                     // 块内偶下标个数
    int odd = 0;                     // 块内奇下标个数
    vector<int>v;                    // 块内所有数值
};

void go(){
    int n, m;cin>>n>>m;
    vector<int>a(n+1);
    DSU dsu(n);

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        dsu.unite(u, v);             // 可交换的两个位置合并
    }

    map<int, node>mp;                // 根 -> 该连通块的统计信息

    for(int i=1;i<=n;i++){
        int f = dsu.find(i);
        mp[f].eve += (i%2==0);       // 下标从 1 开始：偶数下标
        mp[f].odd += (i%2==1);       // 奇数下标
        mp[f].v.pb(a[i]);
    }

    int sum = 0;                     // 所有连通块贡献之和

    for(auto [f, p]: mp){
        auto [eve, odd, arr] = p;
        sort(all(arr), greater<int>());   // 块内数值降序

        // 前 odd 大的放在奇下标取正号，其余放在偶下标取负号
        for(int i=0;i<eve+odd;i++){
            sum += i<odd? arr[i]:-arr[i];
        }
    }

    cout<<sum<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;                         // 本题只有单组数据
    while(_--){
        go();
    }
    return 0;
}