結果
問題 | No.2634 Tree Distance 3 |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-11 17:34:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 826 ms / 3,000 ms |
コード長 | 2,039 bytes |
コンパイル時間 | 2,597 ms |
コンパイル使用メモリ | 209,440 KB |
最終ジャッジ日時 | 2025-02-19 05:13:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 69 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=int(a);i<int(b);i++) #define all(p) p.begin(),p.end() void chmin(int &a,int b){a=min(a,b);} void chmax(int &a,int b){a=max(a,b);} int main(){ int N; cin>>N; vector<int> A(N); rep(i,0,N) cin>>A[i]; vector<vector<int>> G(N); rep(i,0,N-1){ int a,b; cin>>a>>b; a--,b--; G[a].push_back(b); G[b].push_back(a); } int B=0; while((1<<B)<N) B++; B++; vector<int> ans(N); vector<int> depth(N,-1); vector<int> E(N*2); vector table(B,vector<int>(N*2)); int ind=0; auto dfs=[&](auto self,int var) -> void { E[var]=ind++; for(auto x:G[var]){ if(depth[x]==-1){ depth[x]=depth[var]+1; self(self,x); } } E[var+N]=ind++; }; depth[0]=0; dfs(dfs,0); rep(i,0,N){ table[0][E[i]]=depth[i]; table[0][E[i+N]]=depth[i]-1; } rep(i,0,B-1) rep(j,0,N*2){ table[i+1][j]=table[i][j]; if(j+(1<<i)<N*2) chmin(table[i+1][j],table[i][j+(1<<i)]); } auto dist=[&](int a,int b) -> int { if(E[a]>E[b]) swap(a,b); int l=E[a]; int r=E[b]+1; int z=31-__builtin_clz(r-l); return depth[a]+depth[b]-2*min(table[z][l],table[z][r-(1<<z)]); }; // p に含まれるやつから q に含まれるやつの距離を考える // q のやつを更新 auto f=[&](vector<int> p,vector<int> q) -> void { vector<int> X={p[0],p[0],p[0]}; rep(i,0,2) for(auto x:p) if(dist(X[i],X[i+1])<dist(X[i],x)) X[i+1]=x; for(auto x:q) rep(i,1,3) chmax(ans[x],dist(X[i],x)); }; vector<int> order(N); rep(i,0,N) order[i]=i; sort(all(order),[&](int l,int r){ return A[l]<A[r]; }); vector<int> tmp={order[0]}; rep(i,0,N){ if(i==N-1||A[order[i]]!=A[order[i+1]]){ f(tmp,tmp); if(i!=N-1) tmp={order[i+1]}; } else tmp.push_back(order[i+1]); } auto g=[&](auto self,vector<int> p) -> void { int len=p.size(); if(len<=1) return; vector<int> q1,q2; rep(i,0,p.size()){ (i*2<len?q1:q2).push_back(p[i]); } f(q2,q1); self(self,q1); self(self,q2); };g(g,order); rep(i,0,N){ if(i) cout<<" "; cout<<ans[i]; } cout<<"\n"; }