提出 #73921933

---

ソースコード 拡げる

//BEST TEMPLATE EVER
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define nn '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a);i>(b);--i)
#define each(x,a) for(auto& x:a)
#define each2(x,y,a) for(auto& [x,y]:a)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define un_mp unordered_map
#define un_st unordered_set
#define popcnt __builtin_popcountll
#if defined(__GNUC__) || defined(__clang__)
#define AINLINE __attribute__((always_inline)) inline
#else
#define AINLINE inline
#endif

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vstr = vector<string>;
using vll = vector<ll>;
using i128 = __int128_t;

template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_comb(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
//y_comb([&](...) -> type {...}) - рекурсия лямбд внутри другой функции

template<class T> AINLINE istream& operator>>(istream& in, vector<T>& a) { for (auto& x : a) in >> x; return in; }
template<class T> AINLINE ostream& operator<<(ostream& out, const vector<T>& a) { for (int i = 0; i < sz(a); ++i) out << a[i] << " \n"[i + 1 == sz(a)]; return out; }

AINLINE uint64_t splitmix64(uint64_t x) noexcept {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}
static uint64_t sm_state = (uint64_t)chrono::steady_clock::now().time_since_epoch().count() ^ (uint64_t)(uintptr_t)new int;
AINLINE uint64_t rnd() noexcept { sm_state += 0x9e3779b97f4a7c15ULL; return splitmix64(sm_state); }

struct chash {
    static AINLINE uint64_t seed() noexcept { static const uint64_t s = rnd(); return s; }
    AINLINE size_t operator()(uint64_t x) const noexcept { uint64_t sd = seed(); return (size_t)splitmix64(x + sd); }
    AINLINE size_t operator()(int64_t x) const noexcept { uint64_t sd = seed(); return (size_t)splitmix64((uint64_t)x + sd); }
    AINLINE size_t operator()(uint32_t x) const noexcept { uint64_t sd = seed(); return (size_t)splitmix64((uint64_t)x + sd); }
    AINLINE size_t operator()(int32_t x) const noexcept { uint64_t sd = seed(); return (size_t)splitmix64((uint64_t)(int64_t)x + sd); }
    AINLINE size_t operator()(string_view s) const noexcept {
        uint64_t sd = seed();
        const uint8_t* p = (const uint8_t*)s.data();
        size_t n = s.size();
        uint64_t h = splitmix64(sd ^ (uint64_t)n);
        while (n >= 8) {
            uint64_t x;
            memcpy(&x, p, 8);
            h = splitmix64(h ^ (x + sd));
            p += 8; n -= 8;
        }
        if (n) {
            uint64_t x = 0;
            memcpy(&x, p, n);
            h = splitmix64(h ^ (x + sd));
        }
        return (size_t)h;
    }
    AINLINE size_t operator()(const string& s) const noexcept { return (*this)(string_view(s)); }
    AINLINE size_t operator()(const char* s) const noexcept { return (*this)(string_view(s, strlen(s))); }
    template<class A, class B>
    AINLINE size_t operator()(const pair<A, B>& p) const noexcept {
        uint64_t a = (uint64_t)(*this)(p.first);
        uint64_t b = (uint64_t)(*this)(p.second);
        return (size_t)splitmix64(a ^ (b + 0x9e3779b97f4a7c15ULL + (a << 6) + (a >> 2)));
    }
};

template<class K, class V> using hash_map = __gnu_pbds::gp_hash_table<K, V, chash>;
template<class K> using hash_set = __gnu_pbds::gp_hash_table<K, __gnu_pbds::null_type, chash>;
template<class T> using ord_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// order_of_key(x) - сколько меньше x, find_by_order(x) - итератор на элемент на позиции x (0-based)

template<typename T, T MOD>
struct ModInt {
    T v;
    AINLINE ModInt() noexcept : v(0) {}
    template<typename U> AINLINE ModInt(U x) noexcept { set(x); }
    template<typename U>
    AINLINE void set(U x) noexcept {
        if constexpr (std::is_signed_v<U>) {
            __int128 t = (__int128)x % (__int128)MOD;
            if (t < 0) t += MOD;
            v = (T)t;
        }
        else {
            __uint128_t t = (__uint128_t)x % (__uint128_t)MOD;
            v = (T)t;
        }
    }
    AINLINE explicit operator T() const noexcept { return v; }
    friend AINLINE ostream& operator<<(ostream& os, const ModInt& a) { return os << a.v; }
    friend AINLINE istream& operator>>(istream& is, ModInt& a) { long long x; is >> x; a.set(x); return is; }
    AINLINE ModInt& operator+=(const ModInt& o) noexcept { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    AINLINE ModInt& operator-=(const ModInt& o) noexcept { if (v < o.v) v += MOD; v -= o.v; return *this; }
    AINLINE ModInt& operator*=(const ModInt& o) noexcept {
        if constexpr (sizeof(T) <= 4) {
            v = (T)(1ull * v * o.v % MOD);
        } else {
            v = (T)((__int128)v * o.v % MOD);
        }
        return *this; 
    }
    static AINLINE ModInt pow(ModInt a, long long e) noexcept { ModInt r = 1; for (; e; e >>= 1, a *= a) if (e & 1) r *= a; return r; }
    static AINLINE ModInt inv(ModInt a) noexcept { return pow(a, (long long)MOD - 2); }
    AINLINE ModInt& operator/=(const ModInt& o) noexcept { return *this *= inv(o); }
    friend AINLINE ModInt operator+(ModInt a, const ModInt& b) noexcept { return a += b; }
    friend AINLINE ModInt operator-(ModInt a, const ModInt& b) noexcept { return a -= b; }
    friend AINLINE ModInt operator*(ModInt a, const ModInt& b) noexcept { return a *= b; }
    friend AINLINE ModInt operator/(ModInt a, const ModInt& b) noexcept { return a /= b; }
    friend AINLINE bool operator==(const ModInt& a, const ModInt& b) noexcept { return a.v == b.v; }
    friend AINLINE bool operator!=(const ModInt& a, const ModInt& b) noexcept { return a.v != b.v; }
};

AINLINE int msb(ll x) { return x ? 63 - __builtin_clzll((ull)x) : -1; } //старший 1-бит (0 based)
AINLINE int lsb(ll x) { return x ? __builtin_ctzll((ull)x) : -1; } //младший 1-бит (0 based)

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const ld PI = acos(-1.0L);
const ld EPS = 1e-9;
using mint = ModInt<int, MOD>;

template <typename T, typename K>
AINLINE T modpow(T a, K e) { T r = 1; for (; e; e >>= 1, a = (ull)a * a % MOD) if (e & 1) r = (ull)r * a % MOD; return r; }
template <typename T, typename K>
AINLINE T binpow(T a, K e) { T r = 1; for (; e; e >>= 1, a = a * a) if (e & 1) r = r * a; return r; }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

void dfs(int u, const vector<vector<int>>& graph, vector<bool>& visited, multiset<int>&vals, vi&a, vector<bool>&ans, int parent) {
    visited[u] = true;
    if (vals.contains(a[u-1]) || ans[parent]) {
        ans[u] = 1;
    }
    else {
        ans[u] = 0;
    }
    vals.insert(a[u-1]);
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, graph, visited, vals,a,ans,u);
        }
    }
    auto it = vals.find(a[u-1]);
    vals.erase(it);
}

void solve() {
    int n;
    cin >> n;
    vi a(n); cin >> a;
    vector<pair<int,int>> edges(n-1);
    each2(x,y,edges) cin >> x >> y;
    vector<vector<int>> graph(n+1);
    each2(x,y,edges) {
        graph[x].pb(y);
        graph[y].pb(x);
    }
    vector<bool> visited(n+1);
    multiset<int> vals;
    vector<bool> ans(n+1);
    dfs(1, graph, visited, vals,a,ans, 0);
    for (int i=1; i<=n; ++i) cout << (ans[i] ? "Yes":"No") << nn;
}

提出情報

ジャッジ結果