牛牛选路径

约定：称度数为奇数的点为奇点，称度数为偶数的点为偶点。

贪心策略：

对于每一个连通块，考虑以下两种情况：

1. 如果不存在奇点，则选择点权最小的点作为头尾连接一条路径。

2. 存在奇点，则必然有偶数个奇点，只需要选出这些奇点之间的最优匹配，

   而这个最优匹配就是：排序之后不断取最小值和最大值匹配。

证明：

1. 没有奇点时，可以直接提取一条欧拉回路。

2. 存在奇点时，对于任何一个合法的匹配，均存在方案，使得以匹配为头尾的链组，将每条边覆盖奇数次。

   下面给出了一个合法的构造：

   1. 设匹配点集合为$\{u_i,v_i{\}}_{i=1}^k\backslash \{u\_i,v\_i\backslash \}\_\{i=1\}^k$，在$u_i,v_{i}u\_i,v\_i$之间连接一条虚边，记为$e_{i}e\_i$，得到新图$G^{\mathrm{\prime }}G\text{'}$。

      容易在原图上找到某一条$u_i,v_{i}u\_i,v\_i$之间的路径，记作$p_{i}p\_i$。

   2. 在$G^{\mathrm{\prime }}G\text{'}$上求一个欧拉回路$PP$，

      此时容易通过将$e_{i}e\_i$替换为$p_{i}p\_i$的操作将虚边实化，称实化的路径为额外路径，记实化的环为$P^{\mathrm{\prime }}P\text{'}$。

   3. 对于每一个$u_i,v_{i}u\_i,v\_i$，其对应的路径为$P^{\mathrm{\prime }}P\text{'}$删除$p_{i}p\_i$这一段，容易发现路径的头尾是对应的。

      此时，$P^{\mathrm{\prime }}P\text{'}$上的额外路径均比其他路径少被遍历了恰好一次（因为在其对应的$u_i,v_{i}u\_i,v\_i$这里被删除了）。

   4. 如果$P^{\mathrm{\prime }}P\text{'}$上的非额外路径被遍历了偶数次，则在某一条路径中，额外增加一段绕过一整个$P^{\mathrm{\prime }}P\text{'}$的段。

   这样就保证了$P^{\mathrm{\prime }}P\text{'}$上的非额外路径被遍历了奇数次；而额外路径被遍历了偶数次，不产生贡献；

   而$P^{\mathrm{\prime }}P\text{'}$上的非额外路径就对应了原图的所有边，故构造合法。

3. 匹配的最优性：

   设排序之后的奇点点权为$a_1,a_2,\cdots ,a_{2k}a\_1,a\_2,\backslash cdots,a\_\{2k\}$，容易由排序不等式得到证明：

   1. 如果有一个匹配$u,vu,v$，满足$u,v>ku,v>k$，那么就必然存在一个匹配$u^{\mathrm{\prime }},v^{\mathrm{\prime }}u\text{'},v\text{'}$满足$u^{\mathrm{\prime }},v^{\mathrm{\prime }}\le ku\text{'},v\text{'}\backslash leq\; k$。

      由二元排序不等式$a_u{a}_v+a_{u^{\mathrm{\prime }}}{a}_{v^{\mathrm{\prime }}}\ge a_u{a}_{v^{\mathrm{\prime }}}+a_{u^{\mathrm{\prime }}}{a}_{v}a\_ua\_v+a\_\{u\text{'}\}a\_\{v\text{'}\}\backslash ge\; a\_\{u\}a\_\{v\text{'}\}+a\_\{u\text{'}\}a\_v$，此时交换$v,v^{\mathrm{\prime }}v,v\text{'}$总更优。

   2. 排除$11$的情况后，此时问题变成了对于每个$i\le ki\backslash leq\; k$，匹配一个$j>kj>k$。

      那么可以直接分成$[1,k],[k+1,2k][1,k],[k+1,2k]$两个集合，由多元排序不等式得到最优解。

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define P 998244353 
int n,m,a[M],deg[M],sk[M];
vector<int>d[M];
bool cmp(int x,int y){
	return a[x]<a[y];	
}
int main(){
	int mx=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		d[x].push_back(y);
		d[y].push_back(x);
		deg[x]^=1;deg[y]^=1;
	}
	int cnt=0,ans=0;
	for(int i=1;i<=n;++i)if(deg[i])sk[++cnt]=i;
	if(cnt==0){
		ans=1e9;
		for(int i=1;i<=n;++i)ans=min(ans,a[i]*a[i]);
	}else{
		sort(sk+1,sk+cnt+1,cmp);
		for(int i=1;i<=cnt/2;++i)ans+=a[sk[i]]*a[sk[cnt-i+1]];
	}
	printf("%d",ans%P);
}