#include using namespace std; #include using namespace atcoder; //高速化 struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<using vc = vector; templateusing vvc = vc>; templateusing vvvc = vvc>; using vi = vc; using vvi = vvc; using vvvi = vvvc; using vl = vc; using vvl = vvc; using vvvl = vvvc; using pi = pair; using pl = pair; using ull = unsigned ll; templateusing priq = priority_queue; templateusing priqg = priority_queue, greater>; // for文 #define overload4(a, b, c, d, e, ...) e #define rep1(n) for(ll i = 0; i < n; i++) #define rep2(i, n) for(ll i = 0; i < n; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, step) for(ll i = a; i < b; i+= step) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define per1(n) for(ll i = n-1; i >= 0; i--) #define per2(i, n) for(ll i = n-1; i >= 0; i--) #define per3(i, a, b) for(ll i = b-1; i >= a; i--) #define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step) #define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__) #define fore1(a) for(auto&& i : a) #define fore2(i,a) for(auto&& i : a) #define fore3(x,y,a) for(auto&& [x, y] : a) #define fore4(x,y,z,a) for(auto&& [x, y, z] : a) #define fore(...) overload4(__VA_ARGS__, fore4, fore3, fore2, fore1)(__VA_ARGS__) //関数 #define mp make_pair #define mt make_tuple #define a first #define b second #define pb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define si(x) (ll)(x).size() templateinline bool chmax(S& a, T b){return a < b && ( a = b , true);} templateinline bool chmin(S& a, T b){return a > b && ( a = b , true);} templatevoid uniq(vc&a){sort(all(a));a.erase(unique(all(a)),a.end());} templatevc operator++(vc&v,signed){auto res = v;fore(e,v)e++;return res;} templatevc operator--(vc&v,signed){auto res = v;fore(e,v)e--;return res;} templatevc operator++(vc&v){fore(e,v)e++;return v;} templatevc operator--(vc&v){fore(e,v)e--;return v;} //入出力(operator) templateistream&operator>>(istream&is,static_modint&a){ll v;is>>v;a=v;return is;} istream&operator>>(istream&is,modint&a){ll v;cin>>v;a=v;return is;} templateistream&operator>>(istream&is,pair&a){is>>a.a>>a.b;return is;} templateistream&operator>>(istream&is,vc&a){fore(e,a)is>>e;return is;} templateostream&operator<<(ostream&os,static_modinta){return os<ostream&operator<<(ostream&os,pair&a){return os<ostream&operator<<(ostream&os,set&a){fore(it,a){os<ostream&operator<<(ostream&os,multiset&a){fore(it,a){os<ostream&operator<<(ostream&os,map&a){fore(x,y,a){os<ostream&operator<<(ostream&os,unordered_set&a){fore(it,a){os<ostream&operator<<(ostream&os,unordered_map&a){fore(x,y,a){os<ostream&operator<<(ostream&os,vc&a){fore(e,a)os<ostream&operator<<(ostream&os,vvc&a){fore(e,a)os<>a;return a;} vl readvl(ll n){vl a(n);cin>>a;return a;} vvi readg(ll n,ll m,bool bidirected=true){vvi g(n);rep(i,m){ll a,b;cin>>a>>b;a--;b--;g[a].pb(b);if(bidirected)g[b].pb(a);}return g;} vvcreadgc(ll n,ll m,bool bidirected=true){vvc g(n);rep(i,m){ll a,b,c;cin>>a>>b>>c;a--;b--;g[a].pb(b,c);if(bidirected)g[b].pb(a,c);}return g;} vvi readt(ll n,bool bidirected=true){return readg(n,n-1,bidirected);} vvc readtc(ll n,bool bidirected=true){return readgc(n,n-1,bidirected);} inline void yes(){cout << "Yes\n";} inline void no(){cout << "No\n";} inline void yesno(bool y = true){if(y)yes();else no();} inline void print(){cout<inline void print(T a){cout<inline void print(T a,Ts ...b){cout<>t; while(t--)solve(); } class LCA{ private: int root; int k; // n<=2^kとなる最小のk vector> dp; // dp[i][j]:=要素jの2^i上の要素 vector depth; // depth[i]:=rootに対する頂点iの深さ public: LCA(const vector>& _G, const int _root=0){ int n=_G.size(); root=_root; k=1; int nibeki=2; while(nibeki>(k+1, vector(n, -1)); depth.resize(n); function _dfs=[&](int v, int p){ dp[0][v]=p; for(auto nv: _G[v]){ if(nv==p) continue; depth[nv]=depth[v]+1; _dfs(nv, v); } }; _dfs(root, -1); // ダブリング for(int i=0; i>i)&1) u=dp[i][u]; } if(u==v) return u; for(int i=k; i>=0; i--){ if(dp[i][u]!=dp[i][v]){ u=dp[i][u], v=dp[i][v]; } } return dp[0][u]; } int get_distance(const int u, const int v){ int lca=get(u,v); return depth[u]+depth[v]-2*depth[lca]; } }; void solve(){ int n; cin >> n; vi a = readvi(n); vvi t = readt(n); LCA dist(t); vi io(n); iota(all(io), 0); sort(all(io), [&](int l,int r){ return a[l] > a[r]; }); vi st; vi ans(n); int l = io[0],r = io[0]; rep(k,n){ int i = io[k]; if(k == 0 || a[i] != a[io[k-1]]){ rep(L, k, n){ int j = io[L]; if(a[i] != a[j]) break; if(dist.get_distance(j,r) > dist.get_distance(l,r)){ if(dist.get_distance(j,l) < dist.get_distance(j,r)) l = j; else r = j; } if(dist.get_distance(j,l) > dist.get_distance(l,r)) r = j; } } ans[i] = max(dist.get_distance(i,l),dist.get_distance(i,r)); } print(ans); }