fork download

import java.util.*;

import java.io.*;

import java.text.*;

//Solution Credits: Taranpreet Singh

public class Main{

//SOLUTION BEGIN

void pre() throws Exception{}

void solve(int TC) throws Exception{

n = ni();

int[] k = new int[n];

for(int i = 0; i< n; i++)k[i] = ni();

int[][] e = new int[n-1][];

for(int i = 0; i< n-1; i++)e[i] = new int[]{ni()-1, ni()-1};

g = makeU(n, e);

l = new LCA(g);

sz = new int[n];cpar = new int[n];Arrays.fill(cpar, -1);

marked= new boolean[n];

cnt = new int[2][n][];

cpar[decompose(0, -1)] = -1;

for(int i = 0; i< n; i++){

int lo = 0, hi = n;

while(lo<hi){

int mid = (lo+hi)/2;

int x = query(i, mid+2, i);

if(x< k[i])hi = mid;

else lo = mid+1;

}

p(lo+" ");

}

}

LCA l;

int[][] g, cnt[];

int[] sz, cpar;

int n,count = 0;

boolean[] marked;

void predfs(int u, int p){

sz[u] = 1;count++;

for(int v:g[u]){

if(v==p || marked[v])continue;

predfs(v, u);

sz[u]+=sz[v];

}

}

void dfs(int u, int p, int d, int uu, int foo){

cnt[foo][uu][d]++;

for(int v:g[u])

if(!marked[v] && v!=p)

dfs(v, u, d+1, uu, foo);

}

int centroid(int u, int p){

for(int v:g[u])

if(!marked[v] && v!= p && sz[v]>count/2)

return centroid(v, u);

return u;

}

int decompose(int u, int p){

count = 0;

predfs(u, p);

int cen = centroid(u, u);

cpar[cen] = p;

cnt[0][cen] = new int[count];

dfs(cen, -1, 0, cen, 0);

for(int i = count-2; i>=0; i--)

cnt[0][cen][i] += cnt[0][cen][i+1];

if(p!=-1){

cnt[1][cen] = new int[count];

dfs(u, -1, 0, cen, 1);

for(int i = count-2; i>= 0; i--)

cnt[1][cen][i]+=cnt[1][cen][i+1];

}

marked[cen] = true;

for(int v:g[cen])

if(!marked[v] && v!=p)

decompose(v, cen);

marked[cen] = false;

return cen;

}

int query(int u, int di, int node){

int dis = Math.max(0, di-l.dist(u, node));

int ans = 0;

if(dis<cnt[0][u].length)ans+=cnt[0][u][dis];

if(cpar[u]!=-1){

dis = Math.max(0, di-l.dist(cpar[u], node)-1);

if(dis>= 0 && dis<cnt[1][u].length)ans -= cnt[1][u][dis];

}

if(cpar[u]!=-1)ans+=query(cpar[u], di, node);

return ans;

}

final class LCA{

int n = 0, ti= -1;

int[] eu, fi, d;

RMQ rmq;

public LCA(int[][] g){

n = g.length;

eu = new int[2*n-1];fi = new int[n];d = new int[n];

Arrays.fill(fi, -1);Arrays.fill(eu, -1);

dfs(g, 0, -1);

rmq = new RMQ(eu, d);

}

void dfs(int[][] g, int u, int p){

eu[++ti] = u;fi[u] = ti;

for(int v:g[u])if(v!=p){

d[v] = d[u]+1;

dfs(g, v, u);eu[++ti] = u;

}

}

int lca(int u, int v){

return rmq.query(Math.min(fi[u], fi[v]), Math.max(fi[u], fi[v]));}

int dist(int u, int v){

return d[u]+d[v]-2*d[lca(u,v)];

}

class RMQ{

int[] len, d;

int[][] rmq;

public RMQ(int[] a, int[] d){

len = new int[a.length+1];

this.d = d;

for(int i = 2; i<= a.length; i++)len[i] = len[i>>1]+1;

rmq = new int[len[a.length]+1][a.length];

for(int i = 0; i< rmq.length; i++)

for(int j = 0; j< rmq[i].length; j++)

rmq[i][j] = -1;

for(int i = 0; i< a.length; i++)rmq[0][i] = a[i];

for(int b = 1; b<= len[a.length]; b++)

for(int i = 0; i + (1<<b)-1< a.length; i++)

if(d[rmq[b-1][i]]<d[rmq[b-1][i+(1<<(b-1))]])rmq[b][i] =rmq[b-1][i];

else rmq[b][i] = rmq[b-1][i+(1<<(b-1))];

}

int query(int l, int r){

if(l==r)return rmq[0][l];

int b = len[r-l];

if(d[rmq[b][l]]<d[rmq[b][r-(1<<b)]])return rmq[b][l];

return rmq[b][r-(1<<b)];

}

}

}

int[][] makeU(int n, int[][] edge){

int[][] g = new int[n][];int[] cnt = new int[n];

for(int i = 0; i< edge.length; i++){cnt[edge[i][0]]++;cnt[edge[i][1]]++;}

for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];

for(int i = 0; i< edge.length; i++){

g[edge[i][0]][--cnt[edge[i][0]]] = edge[i][1];

g[edge[i][1]][--cnt[edge[i][1]]] = edge[i][0];

}

return g;

}

//SOLUTION END

void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}

long mod = (long)1e9+7, IINF = (long)1e10;

final int INF = (int)1e9, MX = (int)1e4+1;

DecimalFormat df = new DecimalFormat("0.000000000000000");

double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;

static boolean multipleTC = false, memory = false;

FastReader in;PrintWriter out;

void run() throws Exception{

in = new FastReader();

out = new PrintWriter(System.out);

int T = (multipleTC)?ni():1;

//Solution Credits: Taranpreet Singh

pre();for(int t = 1; t<= T; t++)solve(t);

out.flush();

out.close();

}

public static void main(String[] args) throws Exception{

if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();

else new Main().run();

}

long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}

int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}

int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}

void p(Object o){out.print(o);}

void pn(Object o){out.println(o);}

void pni(Object o){out.println(o);out.flush();}

String n()throws Exception{return in.next();}

String nln()throws Exception{return in.nextLine();}

int ni()throws Exception{return Integer.parseInt(in.next());}

long nl()throws Exception{return Long.parseLong(in.next());}

double nd()throws Exception{return Double.parseDouble(in.next());}

 

class FastReader{

BufferedReader br;

StringTokenizer st;

public FastReader(){

br = new BufferedReader(new InputStreamReader(System.in));

}

 

public FastReader(String s) throws Exception{

br = new BufferedReader(new FileReader(s));

}

 

String next() throws Exception{

while (st == null || !st.hasMoreElements()){

try{

st = new StringTokenizer(br.readLine());

}catch (IOException e){

throw new Exception(e.toString());

}

}

return st.nextToken();

}

 

String nextLine() throws Exception{

String str = "";

try{ 

str = br.readLine();

}catch (IOException e){

throw new Exception(e.toString());

} 

return str;

}

}

} 

Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:359: error: illegal character: '\u00a0'
?
^
Main.java:361: error: <identifier> expected
class FastReader{
                ^
Main.java:367: error: invalid method declaration; return type required
public FastReader(){
       ^
Main.java:373: error: illegal character: '\u00a0'
?
^
Main.java:375: error: invalid method declaration; return type required
public FastReader(String s) throws Exception{
       ^
Main.java:381: error: illegal character: '\u00a0'
?
^
Main.java:383: error: invalid method declaration; return type required
String next() throws Exception{
       ^
Main.java:403: error: illegal character: '\u00a0'
?
^
Main.java:405: error: invalid method declaration; return type required
String nextLine() throws Exception{
       ^
Main.java:425: error: class, interface, or enum expected
} 
^
10 errors
stdout
Standard output is empty