E - There Should Be a Lot of Maximums.cpp

#ifdef DEBUG
#include "debug.h"
#endif // DEBUG
#ifndef DEBUG
template <typename T>
void debug(T &x){}
#endif // DEBUG

#include <bits/stdc++.h>

using namespace std;

vector <vector <pair<int, int> > > adj;
vector <vector <int> > ch;
vector <int> a, index, sz, ans;

int maxA;

struct info{
    vector <int> nodes;
    set <int> s;
    int ans1;
    int ans2;

    info(){
         ans1 = maxA;
         ans2 = -1;
    }

    void add(int x){
        if(x == -1) return;
        nodes.push_back(x);
        if(s.find(x) != s.end()){
            ans2 = max(ans2, x);
        }else{
            s.insert(x);
            while(ans1 >= 0 && s.find(ans1) != s.end()) ans1--;
        }
    }

    int query(){
        return max(ans1, ans2);
    }
};

void getIndex(int pos, int par){
    sz[pos] = 1;
    for(auto &p : adj[pos]){
        int nxt = p.first;
        int idx = p.second;
        if(nxt == par) continue;
        index[nxt] = idx;
        getIndex(nxt, pos);
        sz[pos] += sz[nxt];
        ch[pos].push_back(nxt);
    }

    if(!ch[pos].empty()){
        int maxSize = -1, maxP;
        for(int i = 0; i < (int)ch[pos].size(); i++){
            if(sz[ch[pos][i]] > maxSize) maxSize = sz[ch[pos][i]], maxP = i;
        }
        swap(ch[pos][0], ch[pos][maxP]);
    }
}

info* smallToLarge(int pos){
    info* res;
    if(ch[pos].empty()) res = new info();
    else res = smallToLarge(ch[pos][0]);

    for(int i = 1; i < (int)ch[pos].size(); i++){
        info *tmp = smallToLarge(ch[pos][i]);
        for(int p : tmp->nodes) res->add(p);
        delete tmp;
    }

    res->add(a[pos]);

    ans[pos] = res->query();

    return res;
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    adj.resize(n + 1);
    a.resize(n + 1);
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    for(int i = 1; i <= n; i++) cin >> a[i];

    index.resize(n + 1);
    sz.resize(n + 1);
    ch.resize(n + 1);
    getIndex(1, 0);
    debug(index);
    debug(sz);
    debug(ch);

    map <int, int> mp;
    for(int i = 1; i <= n; i++){
        auto res = mp.insert({a[i], 1});
        if(!res.second) res.first->second++;
    }

    int minAns = 0;
    for(int i = 1; i <= n; i++){
        int val = mp[a[i]];
        if(val > 2) minAns = max(minAns, a[i]);
        if(val != 2) a[i] = -1;
    }

    vector <int> comp;
    for(int i = 1; i <= n; i++){
        if(a[i] != -1) comp.push_back(a[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for(int i = 1; i <= n; i++){
        if(a[i] != -1) a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
    }
    debug(a);
    maxA = (int)comp.size() - 1;

    ans.resize(n + 1);
    smallToLarge(1);

    for(int i = 2; i <= n; i++){
        if(ans[i] == -1) ans[i] = 0;
        else ans[i] = comp[ans[i]];
    }

    vector <int> vec(n - 1);
    for(int i = 2; i <= n; i++){
        vec[index[i]] = ans[i];
    }

    for(int i : vec) cout << max(minAns, i) << "\n";
}