Submission #1135192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135192		ByeWorld	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	357 ms	67936 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+30;
const int SQRT = 610;
const int MAXA = 5e5+10;
const int MOD = 1e6+7;
const int INF = 2e9+10;
const int LOG = 19;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a,b); }

int n, h[MAXN];
vector <int> adj[MAXN];
int dep[MAXN], anc[MAXN][LOG+5];

void dfs(int nw, int par){
    anc[nw][0] = par; dep[nw] = dep[par]+1;
    for(auto nx : adj[nw]){
        if(nx == par) continue;
        dfs(nx, nw);
    }
}
int LCA(int x, int y){
    if(dep[x] > dep[y]) swap(x, y);
    for(int i=LOG-1; i>=0; i--){
        if(dep[anc[y][i]] >= dep[x])
            y = anc[y][i];
    }
    if(x==y) return x;
    for(int i=LOG-1; i>=0; i--){
        if(anc[y][i] != anc[x][i])
            y = anc[y][i], x = anc[x][i];
    }
    return anc[x][0];
}
struct dsu {
    int par[MAXN];
    void bd(){
        for(int i=1; i<=n; i++) par[i] = i;
    }
    int f(int x){
        return (par[x]==x ? x : par[x]=f(par[x]));
    }
    bool con(int x, int y){
        return f(x) == f(y);
    }
    void mer(int x, int y){
        x = f(x); y = f(y);
        if(x==y) return;
        par[x] = y;
    }
} DSU;
bool tag[MAXN];
int dp[MAXN];

signed main(){
    cin >> n;
    vector <pii> vec;
    for(int i=1; i<=n; i++){
        cin >> h[i]; vec.pb({h[i],i});
    }
    sort(vec.begin(), vec.end());
    for(int i=1; i<=n-1; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y); adj[y].pb(x);
    }
    DSU.bd();
    dfs(1, 0);
    for(int j=1; j<LOG; j++)
        for(int i=1; i<=n; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];

    for(auto [x, nw] : vec){
        for(auto nx : adj[nw]){
            if(tag[nx]==0) continue;
            int up = DSU.f(nx);
            int lca = LCA(up, nw);
            dp[nw] = max(dp[nw], dp[up] + dep[up]+dep[nw]-2*dep[lca]);
            DSU.mer(up, nw);
        }
        tag[nw] = 1;
    }
    cout << dp[vec.back().se] << '\n';
}   

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26