题解：AT_abc246_g [ABC246G] Game on Tree 3

· · 题解

简单题。

按照结果的 A 从大到小顺序考虑。对于 A 的最大值，青木若想结果比它小，那么至少在到达写有该 A 的节点的父亲时，需要选择把它变成 0。继续递推着，在处理完前面的限制后，发现当前 A 带来的限制可以表示为，在目前写有该 A 的节点的未被选用的祖先中，需选择一个，在到达它时，青木选择这个节点。否则可以逆推出高桥可以得到该 A。当然，可以贪心地推得，最优时选的是深度最大的那一个。那么这样就可以使用并查集维护了，当找不到满足条件的祖先来选择时，答案自然就无法比它更小。

鲜花：出成联赛模拟 T2，O(n\log n) 给 80 部分，把数据范围调成只放 O(n \alpha (n)) 过，想来还是相当有杀伤力的。

#include <bits/stdc++.h>
using namespace std;

inline int rd(){
    char c = getchar();
    while((c > '9' || c < '0') && c != '-') c = getchar();
    int ret = 0; 
    while(c >= '0' && c <= '9') ret = (ret << 3) + (ret << 1) + c - '0', c = getchar();
    return ret;
}

int n;
int father[200002];
vector<int> vec[200002];
void init(int pos,int faa){
    father[pos] = faa;
    for(int i=0;i<vec[pos].size();i++){
        if(vec[pos][i] == faa) continue;
        init(vec[pos][i], pos);
    }
}
pair<int,int> Data[200002];
int fa[200002], cnt[200002], node[2000002];
int getfa(int u){
    if(fa[u] == u) return u;
    fa[u] = getfa(fa[u]);
    return fa[u];
}

int main(){

    n = rd();
    for(register int i=1;i<=n;i++) fa[i] = i, cnt[i] = 1, node[i] = i;
    for(register int i=1;i<=n-1;i++){
        scanf("%d",&Data[i].first);
        Data[i].second = i + 1;
    }
    for(int i=1;i<n;i++){
        int u, v;
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    sort(Data+1,Data+n);
    init(1, 0); 

    register int i;

    for(i=n-1;i>=1;i--){
        int u = getfa(father[Data[i].second]);
        if(node[u] == 0) break;
        if(node[u] == 1) {
            node[u] = 0;
            continue;
        }
        int v = getfa(father[node[u]]);
        int then = node[v];
        if(cnt[u] > cnt[v]) swap(u, v);
        cnt[v] += cnt[u], fa[u] = v;
        node[v] = then;
    }
    printf("%d",Data[i].first);

    return 0;
}