提出 #30680400

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <vector>
#include <algorithm>
namespace nachia{
template<
    class Elem
>
struct LeftistHeap{
private:
    struct Node{
        Node* l = nullptr;
        Node* r = nullptr;
        int height = 1;
        Elem key;
        Node(Elem new_key) : key(new_key) {}
    };
    Node* root;
    int m_size;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <vector>
#include <algorithm>

namespace nachia{

template<
    class Elem
>
struct LeftistHeap{
private:
    struct Node{
        Node* l = nullptr;
        Node* r = nullptr;
        int height = 1;
        Elem key;
        Node(Elem new_key) : key(new_key) {}
    };

    Node* root;
    int m_size;

public:

    LeftistHeap(){
        root = nullptr;
        m_size = 0;
    }

    LeftistHeap(LeftistHeap&& src){
        root = src.root;
        m_size = src.m_size;
        src.root = nullptr;
        src.m_size = 0;
    }

    LeftistHeap& operator=(LeftistHeap&& src){
        root = src.root;
        m_size = src.m_size;
        src.root = nullptr;
        src.m_size = 0;
        return *this;
    }

    void clear(){
        if(root){
            ::std::vector<Node*> p = {root};
            while(p.size()){
                auto c = p.back(); p.pop_back();
                if(c->l) p.push_back(c->l);
                if(c->r) p.push_back(c->r);
                delete(c);
            }
            root = nullptr;
        }
    }

    ~LeftistHeap(){
        clear();
    }

private:
    static Node* meld_node_norecursive(Node* root, Node* anotherroot){
        if(anotherroot == nullptr){
            return root;
        }
        if(root == nullptr){
            root = anotherroot;
            return root;
        }
        ::std::vector<Node*> st;
        st.reserve(root->height + anotherroot->height);
        Node** p1 = &root;
        Node** p2 = &anotherroot;
        while(true){
            if(*p1 == nullptr){
                *p1 = *p2;
                break;
            }
            if((*p1)->key < (*p2)->key) ::std::swap(*p1, *p2);
            st.push_back(*p1);
            p1 = &(*p1)->r;
        }
        auto st_ritr = st.rbegin();
        while(st_ritr != st.rend()){
            Node* c = *st_ritr;
            if(c->l == nullptr){
                std::swap(c->l, c->r);
                c->height = 1;
            }
            else if(c->r == nullptr){
                c->height = 1;
            }
            else{
                if(c->l->height < c->r->height){
                    ::std::swap(c->l, c->r);
                }
                c->height = c->r->height + 1;
            }
            st_ritr++;
        }
        return root;
    }
public:

    void push(const Elem& val){
        Node* new_node = new Node(val);
        root = meld_node_norecursive(root, new_node);
        m_size += 1;
    }

    Elem top(){
        return root->key;
    }

    void pop(){
        auto old_root = root;
        root = meld_node_norecursive(old_root->l, old_root->r);
        delete(old_root);
        m_size -= 1;
    }

    int size(){
        return m_size;
    }

    void meld(LeftistHeap& r){
        root = meld_node_norecursive(root, r.root);
        m_size += r.m_size;
        r.root = nullptr;
        r.m_size = 0;
    }
};

} // namespace nachia

#include <iostream>
#include <queue>
#include <atcoder/modint>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using m32 = atcoder::static_modint<998244353>;

namespace Que{
    using LeftistHeap = nachia::LeftistHeap<int>;
}

int main(){
    int N; cin >> N;
    vector<int> A(N);
    A[0] = 0;
    for(int i=1; i<N; i++) cin >> A[i];

    vector<vector<int>> adj(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> bfs = {0};
    vector<int> P(N, -1);
    rep(i,bfs.size()){
        int p = bfs[i];
        for(int e : adj[p]) if(P[p] != e){
            bfs.push_back(e);
            P[e] = p;
        }
    }

    vector<Que::LeftistHeap> dp(N);

    for(int i=N-1; i>=1; i--){
        int p = bfs[i];
        if(dp[p].size()) dp[p].pop();
        dp[p].push(A[p]);
        dp[P[p]].meld(dp[p]);
    }

    if(dp[0].size()) dp[0].pop();
    int ans = (dp[0].size() ? dp[0].top() : 0);
    cout << ans << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

提出情報

ジャッジ結果