• Sources：E - 合成大西瓜
• Abstract：給定由 \(n\) 個點、\(m\) 條邊構成的簡單無向圖( \(n\) 為奇數)，每個點具有點權 \(a_i\)。將進行 \(\frac{n-1}{2}\) 次合并操作，最終圖中僅剩 \(1\) 個點，求該點的最大點權。每次操作如下：
  • 選擇三個不同的點 \(x,y,z\) ，當且僅當 \((x,y),(y,z)\)；
  • 合并后的點為 \(w\) ，其點權 \(a_w=\max(a_y,\min(a_x,a_z))\)；
  • 對于點 \(t\)，當且僅當 \((t,x)\) 或 \((t,y)\) 或 \((t,z)\) ，建立 \((w,t)\)；
  • 刪除點 \(x,y,z\) 及某端為 \(x,y,z\) 的無向邊。
• Keywords：圖論，貪心(簽到題)
• Solution：觀察合并公式發現三點可組織為樹形結構，\(y\) 為根節點，\(x,z\) 為葉子節點。為最大化最終點權，因此貪心：對于度為 \(1\) 的點，最終能保留的是次大值；度 \(\ge 2\) 的點，最終能保留的是最大值。
• Code：

/*
 * Copyright (c) 2025 - Yerosius All Rights Reserved.
 * @Author: Yerosius
 * @Date: 2025-02-16 14:53:33
 * @FilePath: /VSCodeProject/E_合成大西瓜.cpp
 */
#include<bits/stdc++.h>

using namespace std;
using ll=long long;
#define int ll
#define endl "\n"
int n,m;
void solve(){
    vector<int>w(n+1),du(n+1);
    for(int i=1;i<=n;i++) cin>>w[i];
    while(m--){
        int a,b;cin>>a>>b;
        du[a]++,du[b]++;
    }
    int leafmax=0,leafans=0,notleaf=0;
    for(int i=1;i<=n;i++){
        if(du[i]==1){
            if(w[i]>leafmax) leafans=leafmax,leafmax=w[i];
            else leafans=max(leafans,w[i]);
        }else notleaf=max(notleaf,w[i]);
    }
    if(leafans==0) cout<<notleaf;
    else if(notleaf==0) cout<<leafans;
    else cout<<max(leafans,notleaf);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    solve();
    return 0;
}