题解：P13572 [CCPC 2024 重庆站] 合成大西瓜

· · 题解

THUPC 2025「场内口胡大队，但是三三复活」RP++.

考虑判断留下某个点是否可以做到。

我们把这个预期留下的点视作根然后跑 bfs 树。

如果要留下的这个点的度数不为 1，可以对于每一个相连的点先令其对自己的子树进行删除，怎么删都可以，直到每个子树剩下不超过 2 个点。

因为 n 保证是奇数，所以一定可以以根为中心点不断操作直至结束，这样答案一定不小于根，所以可以成为答案。

如果度数为 1 呢？此时这个点无法作为中心点操作。

它能够被保留当且仅当它操作时另一个非中心点大于它。

那么可以把最大值保留过来作为另一个非中心点操作，将最大值作为根跑一个仿照上面东西的算法，但是把当前点留下，最后一步让这两个点合并，答案一定不小于我们预定的这个点。

综上，一个点不可选当且仅当除了自己所有点都小于该点且度数为 1。

特判样例二。

于是做完了。

#include<bits/stdc++.h>
using namespace std;
int ans;
int a[100005];
int f[100005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    ans=a[1];
    while(m--){
        int u,v;
        cin>>u>>v;
        f[u]++;
        f[v]++;
        if(f[u]>1)ans=max(ans,a[u]);
        if(f[v]>1)ans=max(ans,a[v]);
    }
    sort(a+1,a+1+n);
    cout<<max(a[n-1],ans);
    return 0;
}
// 写这篇后记的时候，这个世界正面临各种动荡不安。我衷心盼望这本书送到各位读者手上之际，情况能稍微好转一些。
// 那么，但愿我们能再度于那片令人怀念的天空之下相见。

// 二〇二〇年　春
// 枯野 瑛