結果
| 問題 | No.3660 LIS on Tree |
| コンテスト | |
| ユーザー |
 Falcon_
|
| 提出日時 | 2026-08-30 14:05:52 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,761 bytes |
| 記録 | |
| コンパイル時間 | 2,808 ms |
| コンパイル使用メモリ | 307,944 KB |
| 実行使用メモリ | 18,968 KB |
| 最終ジャッジ日時 | 2026-08-30 14:06:44 |
| 合計ジャッジ時間 | 4,784 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 WA * 1 |
ソースコード
//give me AC!!!!!!!!!//
/*#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")*/
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <numeric>
#include <array>
#include <chrono>
using namespace std;
//delete on codeforces
/*
#include <boost/dynamic_bitset.hpp>
#include <atcoder/all>
using boost::dynamic_bitset;
using namespace atcoder;
using mint = modint998244353;
*/
//end
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
typedef vector<vi> vvi;
#define vl vector<ll>
#define out(x) cout << x << endl
#define Yes(p) out((p ? "Yes":"No"))
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back
template <typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define so(x) sort(x.begin(), x.end());
#define iINF 2147483647
constexpr int mod = 998244353;
//delete on atcoder
struct mint {
int x;
mint(ll x_ = 0) : x(x_ % mod) {
if(x < 0) x += mod;
}
mint operator-() {
auto res = *this;
res.x = (x ? mod - x : 0);
return res;
}
mint& operator+=(mint r) {
if((x += r.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(mint r) {
if((x -= r.x) < 0) x += mod;
return *this;
}
mint& operator*=(mint r) {
x = 1LL * x * r.x % mod;
return *this;
}
mint& operator/=(mint r) { return *this *= r.inv(); }
friend mint operator+(mint a, mint b) { return a += b; }
friend mint operator-(mint a, mint b) { return a -= b; }
friend mint operator*(mint a, mint b) { return a *= b; }
friend mint operator/(mint a, mint b) { return a /= b; }
mint inv() const { return pow(mod - 2); }
mint pow(ll b) const {
mint a = *this, c = 1;
while(b) {
if(b & 1) c *= a;
a *= a;
b >>= 1;
}
return c;
}
};
//end
using vm = vector<mint>;
template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
_() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;
long long inf = 45e17 + 11;
long double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986260348253421170679;
typedef pair<long long, long long > P;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
long long gcd(long long a, long long b) {
if (b == 0)return a;
while (a % b != 0) {
long long u = a % b;
a = b;
b = u;
}
return b;
}
long long lcm(long long x, long long y) {
return x / gcd(x, y) * y;
}
const int MAX = 1000010;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
template <typename T>
struct BIT {
int n; // 配列の要素数(数列の要素数+1)
vector<T> bit; // データの格納先
BIT(int n_) : n(n_ + 1), bit(n, 0) {}
// 1-index
void add(int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[idx] += x;
}
}
// 1-index
T sum(int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[idx];
}
return s;
}
// [l,r) の区間和を取得
T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
int lower_bound(T w) { // a_1 + a_2 + ... + a_x >= w となるような最小の x を求める(ただし a_i >= 0)
if (w <= 0) {
return 0;
}
else {
int x = 0, r = 1;
while (r < n) r = r << 1;
for (int len = r; len > 0; len = len >> 1) { // 長さlenは1段下るごとに半分に
if (x + len < n && bit[x + len] < w) { // 採用するとき
w -= bit[x + len];
x += len;
}
}
return x + 1;
}
}
};
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
struct Edge {
long long to;
long long cost;
};
using Graph = vector<vector<Edge>>;
/* dijkstra(G,s,dis)
入力：グラフ G, 開始点 s, 距離を格納する dis
計算量：O(|E|log|V|)
副作用：dis が書き換えられる
*/
void dijkstra(const Graph& G, int s, vector<long long>& dis) {
int N = G.size();
dis.resize(N, inf);
priority_queue<P, vector<P>, greater<P>> pq; // 「仮の最短距離, 頂点」が小さい順に並ぶ
dis[s] = 0;
pq.emplace(dis[s], s);
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int v = p.second;
if (dis[v] < p.first) { // 最短距離で無ければ無視
continue;
}
for (auto& e : G[v]) {
if (dis[e.to] > dis[v] + e.cost) { // 最短距離候補なら priority_queue に追加
dis[e.to] = dis[v] + e.cost;
pq.emplace(dis[e.to], e.to);
}
}
}
}
long long power(long long x, long long n, long long m = mod) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % m; // n の最下位bitが 1 ならば x^(2^i) をかける
x = x * x % m;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
struct UnionFind {
vector<int> par, size;
vector<int>color;
UnionFind(int x) {
par.resize(x);
size.resize(x, 1);
color.resize(x, 0);
for (int i = 0; i < x; i++) {
par[i] = i;
}
}
int find(int x) {
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
int consize(int x) {
return size[find(x)];
}
int concolor(int x) {
return color[find(x)];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
if (size[x] < size[y]) {
par[x] = y;
size[y] += size[x];
color[y] += color[x];
}
else {
par[y] = x;
size[x] += size[y];
color[x] += color[y];
}
}
};
#define int long long
struct S {
int size;
int left;
int right;
};
struct F {
int a;
};
S op(S a, S b) {
S c;
c.size=a.size+b.size;
c.left=b.left;
c.right=a.right;
if(b.right>a.left){
c.right+=b.right-a.left;
}
else{
c.left+=a.left-b.right;
}
return {
c
};
}
S e() {
return { 0 ,0,0};
}
/*
S mapping(F f, S x) {
return S{
x.a+f.a
};
}
F composition(F f, F g) {
return F{ f.a+g.a };
}
F id() {
return F{ 0 };
}
*/
int op_sum(int a, int b) {return a + b;}
int e_sum() {return 0;}
int op_max(int a, int b) {return max(a, b);}
int e_max() {return 0;}
int op_min(int a, int b) {return min(a, b);}
int e_min() {return (int)(1e9);}
/*
string solve(int N,int K,vector<string>&t){
}
string debug(int N,int K,vector<string>&t){
}*/
signed main()
{
random_device seed_gen;
mt19937_64 rnd(seed_gen());
int N;cin>>N;
vector<int>A(N);
priority_queue<pair<int,int>>pq;
for(int i=0;i<N;i++){
cin>>A[i];
pq.push({A[i],i});
}
vector<vector<int>>G(N);
for(int i=0;i<N-1;i++){
int a,b;cin>>a>>b;
a--;
b--;
if(A[a]<A[b]){
G[a].push_back(b);
}
else{
G[b].push_back(a);
}
}
vector<int>ans(N);
int answer=0;
while(!pq.empty()){
auto[now,idx]=pq.top();
pq.pop();
int here=0;
for(auto i:G[idx]){
here=max(here,ans[i]);
}
ans[idx]=now+here;
answer=max(answer,ans[idx]);
}
cout<<answer<<endl;
}