(Analysis by Nick Wu)

We start by doing a preorder traversal over the tree. By performing a preorder traversal of the tree, we guarantee that for a given node, the descendants of the node all immediately follow the given node in the preorder traversal order. Therefore, the given problem reduces to solving the problem on an array, which is simpler than solving the problem on an arbitrary tree.

To solve the problem on an array, we process the values in decreasing order and maintain a binary indexed tree of which indices have already been processed to count how many descendants exceed a given node.

import java.io.*;
import java.util.*;
public class promote {

static int[] size;
static int[] start;

public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("promote.out")));
for(int i = 0; i < n; i++) {
}
State[] l = new State[n];
for(int i = 0; i < n; i++) {
}
Arrays.sort(l);
for(int i = 1; i < n; i++) {
}
size = new int[n];
start = new int[n];
dfs(0);
int[] ret = new int[n];
BIT bit = new BIT(n);
for(State out: l) {
int rhs = start[out.index] + size[out.index] - 1;
int lhs = start[out.index];
ret[out.index] = bit.query(rhs) - bit.query(lhs);
bit.increment(start[out.index]);
}
for(int out: ret) {
pw.println(out);
}
pw.close();
}

static int numSeen = 0;
public static void dfs(int index) {
start[index] = numSeen++;
size[index]++;
for(int out: children[index]) {
dfs(out);
size[index] += size[out];
}
}

static class State implements Comparable<State> {
public int index, val;

public State(int index, int val) {
this.index = index;
this.val = val;
}

public int compareTo(State s) {
return s.val - val;
}

}

static class BIT {
int[] leaf;
public BIT(int s) {
leaf = new int[s+5];
}
public void increment(int x) {
x+=2;
while(x < leaf.length) {
leaf[x]++;
x += x & -x;
}
}
public int query(int x) {
int ret = 0;
x+=2;
while(x > 0) {
ret += leaf[x];
x -= x & -x;
}
return ret;
}
}

}