제출 #742983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742983		zaneyu	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	440 ms	55828 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
vector<int> g[maxn];
vector<pii> v;
ll dp[maxn];
int arr[maxn];
int dep[maxn];
struct uf{
	int par[maxn],rank1[maxn],mx[maxn];
	void init(int n){
		REP(i,n) par[i]=i,rank1[i]=1,mx[i]=i;
	}
	int find(int u){
		if(par[u]==u) return u;
		return par[u]=find(par[u]);
	}
	void merge(int a,int b){
		a=find(a),b=find(b);
		if(a==b) return;
		if(rank1[a]>rank1[b]) swap(a,b);
		rank1[b]+=rank1[a];
		par[a]=b;
		if(arr[mx[a]]>arr[mx[b]]) mx[b]=mx[a];
		
	}
}uf;
int par[maxn][20];
void dfs(int u,int p){
	par[u][0]=p;
	for(int x:g[u]){
		if(x==p) continue;
		dep[x]=dep[u]+1;
		dfs(x,u);
	}
}
int lca(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	int d=dep[a]-dep[b];
	while(d){
		a=par[a][__lg(lowb(d))];
		d-=lowb(d);
	}
	if(a==b){
		return a;
	}
	for(int j=19;j>=0;j--){
		if(par[a][j]!=par[b][j]){
			a=par[a][j],b=par[b][j];
		}
	}
	return par[a][0];
}
int get(int a,int b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int main(){
	int n;
	cin>>n;
	
	REP(i,n){
		int x;
		cin>>x;
		--x;
		v.pb({x,i});
		arr[i]=x;
	}
	uf.init(n);
	REP(i,n-1){
		int a,b;
		cin>>a>>b;
		--a,--b;
		g[a].pb(b),g[b].pb(a);
	}
	dfs(0,-1);
	REP1(j,19){
		REP(i,n){
			if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
			else par[i][j]=-1;
		}
	}
	sort(ALL(v));
	for(auto x:v){
		for(int a:g[x.s]){
			if(arr[a]>x.f) continue;
			int p=uf.mx[uf.find(a)];
			MXTO(dp[x.s],dp[p]+get(x.s,p));
			uf.merge(a,x.s);
		}
		//cout<<dp[x.s]<<' ';
	}
	cout<<dp[v.back().s];
}

• 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