fork download
copy 
  1.  
  2.  
  3. import java.util.*;
  4.  
  5. import java.io.*;
  6.  
  7. import java.text.*;
  8.  
  9. //Solution Credits: Taranpreet Singh
  10.  
  11. public class Main{
  12.  
  13. //SOLUTION BEGIN
  14.  
  15. void pre() throws Exception{}
  16.  
  17. void solve(int TC) throws Exception{
  18.  
  19. n = ni();
  20.  
  21. int[] k = new int[n];
  22.  
  23. for(int i = 0; i< n; i++)k[i] = ni();
  24.  
  25. int[][] e = new int[n-1][];
  26.  
  27. for(int i = 0; i< n-1; i++)e[i] = new int[]{ni()-1, ni()-1};
  28.  
  29. g = makeU(n, e);
  30.  
  31. l = new LCA(g);
  32.  
  33. sz = new int[n];cpar = new int[n];Arrays.fill(cpar, -1);
  34.  
  35. marked= new boolean[n];
  36.  
  37. cnt = new int[2][n][];
  38.  
  39. cpar[decompose(0, -1)] = -1;
  40.  
  41. for(int i = 0; i< n; i++){
  42.  
  43. int lo = 0, hi = n;
  44.  
  45. while(lo<hi){
  46.  
  47. int mid = (lo+hi)/2;
  48.  
  49. int x = query(i, mid+2, i);
  50.  
  51. if(x< k[i])hi = mid;
  52.  
  53. else lo = mid+1;
  54.  
  55. }
  56.  
  57. p(lo+" ");
  58.  
  59. }
  60.  
  61. }
  62.  
  63. LCA l;
  64.  
  65. int[][] g, cnt[];
  66.  
  67. int[] sz, cpar;
  68.  
  69. int n,count = 0;
  70.  
  71. boolean[] marked;
  72.  
  73. void predfs(int u, int p){
  74.  
  75. sz[u] = 1;count++;
  76.  
  77. for(int v:g[u]){
  78.  
  79. if(v==p || marked[v])continue;
  80.  
  81. predfs(v, u);
  82.  
  83. sz[u]+=sz[v];
  84.  
  85. }
  86.  
  87. }
  88.  
  89. void dfs(int u, int p, int d, int uu, int foo){
  90.  
  91. cnt[foo][uu][d]++;
  92.  
  93. for(int v:g[u])
  94.  
  95. if(!marked[v] && v!=p)
  96.  
  97. dfs(v, u, d+1, uu, foo);
  98.  
  99. }
  100.  
  101. int centroid(int u, int p){
  102.  
  103. for(int v:g[u])
  104.  
  105. if(!marked[v] && v!= p && sz[v]>count/2)
  106.  
  107. return centroid(v, u);
  108.  
  109. return u;
  110.  
  111. }
  112.  
  113. int decompose(int u, int p){
  114.  
  115. count = 0;
  116.  
  117. predfs(u, p);
  118.  
  119. int cen = centroid(u, u);
  120.  
  121. cpar[cen] = p;
  122.  
  123. cnt[0][cen] = new int[count];
  124.  
  125. dfs(cen, -1, 0, cen, 0);
  126.  
  127. for(int i = count-2; i>=0; i--)
  128.  
  129. cnt[0][cen][i] += cnt[0][cen][i+1];
  130.  
  131. if(p!=-1){
  132.  
  133. cnt[1][cen] = new int[count];
  134.  
  135. dfs(u, -1, 0, cen, 1);
  136.  
  137. for(int i = count-2; i>= 0; i--)
  138.  
  139. cnt[1][cen][i]+=cnt[1][cen][i+1];
  140.  
  141. }
  142.  
  143. marked[cen] = true;
  144.  
  145. for(int v:g[cen])
  146.  
  147. if(!marked[v] && v!=p)
  148.  
  149. decompose(v, cen);
  150.  
  151. marked[cen] = false;
  152.  
  153. return cen;
  154.  
  155. }
  156.  
  157. int query(int u, int di, int node){
  158.  
  159. int dis = Math.max(0, di-l.dist(u, node));
  160.  
  161. int ans = 0;
  162.  
  163. if(dis<cnt[0][u].length)ans+=cnt[0][u][dis];
  164.  
  165. if(cpar[u]!=-1){
  166.  
  167. dis = Math.max(0, di-l.dist(cpar[u], node)-1);
  168.  
  169. if(dis>= 0 && dis<cnt[1][u].length)ans -= cnt[1][u][dis];
  170.  
  171. }
  172.  
  173. if(cpar[u]!=-1)ans+=query(cpar[u], di, node);
  174.  
  175. return ans;
  176.  
  177. }
  178.  
  179. final class LCA{
  180.  
  181. int n = 0, ti= -1;
  182.  
  183. int[] eu, fi, d;
  184.  
  185. RMQ rmq;
  186.  
  187. public LCA(int[][] g){
  188.  
  189. n = g.length;
  190.  
  191. eu = new int[2*n-1];fi = new int[n];d = new int[n];
  192.  
  193. Arrays.fill(fi, -1);Arrays.fill(eu, -1);
  194.  
  195. dfs(g, 0, -1);
  196.  
  197. rmq = new RMQ(eu, d);
  198.  
  199. }
  200.  
  201. void dfs(int[][] g, int u, int p){
  202.  
  203. eu[++ti] = u;fi[u] = ti;
  204.  
  205. for(int v:g[u])if(v!=p){
  206.  
  207. d[v] = d[u]+1;
  208.  
  209. dfs(g, v, u);eu[++ti] = u;
  210.  
  211. }
  212.  
  213. }
  214.  
  215. int lca(int u, int v){
  216.  
  217. return rmq.query(Math.min(fi[u], fi[v]), Math.max(fi[u], fi[v]));}
  218.  
  219. int dist(int u, int v){
  220.  
  221. return d[u]+d[v]-2*d[lca(u,v)];
  222.  
  223. }
  224.  
  225. class RMQ{
  226.  
  227. int[] len, d;
  228.  
  229. int[][] rmq;
  230.  
  231. public RMQ(int[] a, int[] d){
  232.  
  233. len = new int[a.length+1];
  234.  
  235. this.d = d;
  236.  
  237. for(int i = 2; i<= a.length; i++)len[i] = len[i>>1]+1;
  238.  
  239. rmq = new int[len[a.length]+1][a.length];
  240.  
  241. for(int i = 0; i< rmq.length; i++)
  242.  
  243. for(int j = 0; j< rmq[i].length; j++)
  244.  
  245. rmq[i][j] = -1;
  246.  
  247. for(int i = 0; i< a.length; i++)rmq[0][i] = a[i];
  248.  
  249. for(int b = 1; b<= len[a.length]; b++)
  250.  
  251. for(int i = 0; i + (1<<b)-1< a.length; i++)
  252.  
  253. if(d[rmq[b-1][i]]<d[rmq[b-1][i+(1<<(b-1))]])rmq[b][i] =rmq[b-1][i];
  254.  
  255. else rmq[b][i] = rmq[b-1][i+(1<<(b-1))];
  256.  
  257. }
  258.  
  259. int query(int l, int r){
  260.  
  261. if(l==r)return rmq[0][l];
  262.  
  263. int b = len[r-l];
  264.  
  265. if(d[rmq[b][l]]<d[rmq[b][r-(1<<b)]])return rmq[b][l];
  266.  
  267. return rmq[b][r-(1<<b)];
  268.  
  269. }
  270.  
  271. }
  272.  
  273. }
  274.  
  275. int[][] makeU(int n, int[][] edge){
  276.  
  277. int[][] g = new int[n][];int[] cnt = new int[n];
  278.  
  279. for(int i = 0; i< edge.length; i++){cnt[edge[i][0]]++;cnt[edge[i][1]]++;}
  280.  
  281. for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
  282.  
  283. for(int i = 0; i< edge.length; i++){
  284.  
  285. g[edge[i][0]][--cnt[edge[i][0]]] = edge[i][1];
  286.  
  287. g[edge[i][1]][--cnt[edge[i][1]]] = edge[i][0];
  288.  
  289. }
  290.  
  291. return g;
  292.  
  293. }
  294.  
  295. //SOLUTION END
  296.  
  297. void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
  298.  
  299. long mod = (long)1e9+7, IINF = (long)1e10;
  300.  
  301. final int INF = (int)1e9, MX = (int)1e4+1;
  302.  
  303. DecimalFormat df = new DecimalFormat("0.000000000000000");
  304.  
  305. double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
  306.  
  307. static boolean multipleTC = false, memory = false;
  308.  
  309. FastReader in;PrintWriter out;
  310.  
  311. void run() throws Exception{
  312.  
  313. in = new FastReader();
  314.  
  315. out = new PrintWriter(System.out);
  316.  
  317. int T = (multipleTC)?ni():1;
  318.  
  319. //Solution Credits: Taranpreet Singh
  320.  
  321. pre();for(int t = 1; t<= T; t++)solve(t);
  322.  
  323. out.flush();
  324.  
  325. out.close();
  326.  
  327. }
  328.  
  329. public static void main(String[] args) throws Exception{
  330.  
  331. if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
  332.  
  333. else new Main().run();
  334.  
  335. }
  336.  
  337. long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
  338.  
  339. int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
  340.  
  341. int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
  342.  
  343. void p(Object o){out.print(o);}
  344.  
  345. void pn(Object o){out.println(o);}
  346.  
  347. void pni(Object o){out.println(o);out.flush();}
  348.  
  349. String n()throws Exception{return in.next();}
  350.  
  351. String nln()throws Exception{return in.nextLine();}
  352.  
  353. int ni()throws Exception{return Integer.parseInt(in.next());}
  354.  
  355. long nl()throws Exception{return Long.parseLong(in.next());}
  356.  
  357. double nd()throws Exception{return Double.parseDouble(in.next());}
  358.  
  359.  
  360.  
  361. class FastReader{
  362.  
  363. BufferedReader br;
  364.  
  365. StringTokenizer st;
  366.  
  367. public FastReader(){
  368.  
  369. br = new BufferedReader(new InputStreamReader(System.in));
  370.  
  371. }
  372.  
  373.  
  374.  
  375. public FastReader(String s) throws Exception{
  376.  
  377. br = new BufferedReader(new FileReader(s));
  378.  
  379. }
  380.  
  381.  
  382.  
  383. String next() throws Exception{
  384.  
  385. while (st == null || !st.hasMoreElements()){
  386.  
  387. try{
  388.  
  389. st = new StringTokenizer(br.readLine());
  390.  
  391. }catch (IOException e){
  392.  
  393. throw new Exception(e.toString());
  394.  
  395. }
  396.  
  397. }
  398.  
  399. return st.nextToken();
  400.  
  401. }
  402.  
  403.  
  404.  
  405. String nextLine() throws Exception{
  406.  
  407. String str = "";
  408.  
  409. try{ 
  410.  
  411. str = br.readLine();
  412.  
  413. }catch (IOException e){
  414.  
  415. throw new Exception(e.toString());
  416.  
  417. } 
  418.  
  419. return str;
  420.  
  421. }
  422.  
  423. }
  424.  
  425. } 
  426.  
  427.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/hwkgw1
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!