Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //----------------------------------- DEBUG -----------------------------------
- #define sim template < class c
- #define ris return * this
- #define dor > debug & operator <<
- #define eni(x) sim > typename \
- enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
- sim > struct rge { c b, e; };
- sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
- sim > auto dud(c* x) -> decltype(cerr << *x, 0);
- sim > char dud(...);
- struct debug {
- #ifdef LOCAL
- ~debug() { cerr << endl; }
- eni(!=) cerr << boolalpha << i; ris; }
- eni(==) ris << range(begin(i), end(i)); }
- sim, class b dor(pair < b, c > d) {
- ris << "(" << d.first << ", " << d.second << ")";
- }
- sim dor(rge<c> d) {
- *this << "[";
- for (auto it = d.b; it != d.e; ++it)
- *this << ", " + 2 * (it == d.b) << *it;
- ris << "]";
- }
- #else
- sim dor(const c&) { ris; }
- #endif
- };
- #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
- //----------------------------------- END DEBUG --------------------------------
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #define trav(a,x) for (auto& a : x)
- #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
- //----------------------------------- DEFINES -----------------------------------
- #define sz(x) (int)(x).size()
- #define mp make_pair
- #define eb emplace_back
- #define pb push_back
- #define lb lower_bound
- #define ub upper_bound
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define ins insert
- #define nl '\n'
- //----------------------------------- END DEFINES --------------------------------
- //-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------
- struct custom_hash{
- static uint64_t splitmix64(uint64_t x){
- x += 0x9e3779b97f4a7c15;
- x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
- x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
- return x ^ (x >> 31);
- }
- size_t operator()(uint64_t a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- return splitmix64(a + FIXED_RANDOM);
- }
- template<class T> size_t operator()(T a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- hash<T> x;
- return splitmix64(x(a) + FIXED_RANDOM);
- }
- template<class T, class H> size_t operator()(pair<T, H> a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- hash<T> x;
- hash<H> y;
- return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
- }
- };
- template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
- //----------------------- CUSTOM UNORDERED MAP HASH END--------------------------
- vector<int> primes;
- void preprocess() {
- vector<bool> seive(1000100, true);
- seive[0] = seive[1] = false;
- for(int i=2;i*i<1000100;i++) {
- if(seive[i]) {
- for(int j=i*i;j<1000100;j+=i) {
- seive[j] = false;
- }
- }
- }
- for(int i=2;i<1000100;i++) {
- if(seive[i]) primes.push_back(i);
- }
- }
- vector<vector<int>> adj;
- vector<int> final_score, initial_score, transition_score, final_node;
- void dfs(int node, int par) {
- int min_score = final_score[node];
- int curr_node = node;
- for(int child: adj[node]) {
- if(child != par) {
- dfs(child, node);
- if(final_score[child] < min_score) {
- min_score = final_score[child];
- curr_node = final_node[child];
- }
- else if(final_score[child] == min_score) {
- if(curr_node > final_node[child]) {
- curr_node = final_node[child];
- }
- }
- }
- }
- final_node[node] = curr_node;
- final_score[node] = min_score;
- }
- void run_cases() {
- int n;
- cin >> n;
- vector<int> a(n + 1);
- adj = vector<vector<int>>(n + 1);
- final_score = vector<int>(n + 1);
- initial_score = vector<int>(n + 1);
- transition_score = vector<int>(n + 1);
- final_node = vector<int>(n + 1);
- for(int i=1;i<=n;i++) {
- cin >> initial_score[i];
- transition_score[i] = primes[int(upper_bound(all(primes), initial_score[i]) - primes.begin()) - 1];
- final_score[i] = transition_score[i];
- final_node[i] = i;
- }
- for(int i=1;i<n;i++) {
- int u,v;
- cin >> u >> v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- dfs(1, 1);
- for(int i=1;i<=n;i++) {
- cout << final_node[i] << " " << initial_score[i] - final_score[i] << nl;
- }
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(nullptr);
- preprocess();
- int tests = 1;
- // cin >> tests;
- for(int test = 1;test <= tests;test++) {
- run_cases();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement