• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# G – Game on Tree 2（对抗搜索 + 对顶堆维护中位数）

1天前 2次浏览

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 1e5+10;

int n, m;
int dp[maxn];
int a[maxn];
vector<int> G[maxn];

namespace DDD {
multiset<int, less<int> > big;
multiset<int, greater<int> > small;
//int k;
int cnt; ///只求中位数
void init(int kk=1) {
small.clear();
big.clear();
//k = kk;
cnt = 0;
}
void balance() {
///维持上方小根堆比下面大根堆 多k (奇偶会不为k)
while (big.size() > small.size() + (cnt%2==0)) {
small.insert(*big.begin());
big.erase(big.begin());
}
while (small.size() + (cnt%2==0) > big.size()) {
big.insert(*small.begin());
small.erase(small.begin());
}
}
void _insert(int x) {
if (big.size() == 0 || x >= *big.begin()) {
big.insert(x);
}
else {
small.insert(x);
}
balance();
cnt ++;
}
int get() {
//        cout << "in small: ";
//        for (auto i : small ) {
//            cout << i << " ";
//        }
//        cout << endl;
//        cout << "in big: ";
//        for (auto i : big) {
//            cout << i << " ";
//        }
//        cout << endl;
if (cnt % 2) return *big.begin();
return (*small.begin() + *big.begin()) / 2;
}

void _delete(int x) {
auto p1 = small.find(x);
auto p2 = big.find(x);
if (p1 != small.end()) {
small.erase(p1);
balance();
cnt --;
}
else if (p2 != big.end()) {
big.erase(p2);
balance();
cnt --;
}

}
};

void DFS(int u, int fa, int d) {
//    cout << "node: " << u << endl;
DDD::_insert(a[u]);
int mx = 0, mi = 1e9;
for (auto v : G[u]) {
if (v == fa) continue;
DFS(v, u, d+1);
mi = min(dp[v], mi);
mx = max(dp[v], mx);
}
if (mx == 0) {
dp[u] = DDD::get();
//        cout << u << " " << dp[u] << endl;
}
else if (d&1) dp[u] = mi;
else dp[u] = mx;
DDD::_delete(a[u]);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n-1; ++ i) {
int u, v;scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DDD::init();
DFS(1, 0, 0);
cout << dp[1] << endl;
return 0;
}```