算法实现：一次dfs + 求和indexed tree的多次update，query完成

    1. 由于要查找所有祖先节点的值，比自己大的个数，dfs过程中，祖先节点可大，可小求和有困难，所以使用indexed tree来求和
    2. 对每个节点来说其实是求一个自身到根节点的区间中比自己大的个数的和
    3. 并且为了只走一次dfs，所以当进入V节点时，update(V,1),离开节点时update(V,-1)，保证了祖先节点不会重复计算
    4. 注意：栈内存给3M的话，20个case都能通过，本社那边的case可能数据量较大，所以把dfs修改为使用stack的非递归实现

    测试用例：
    2
    7 7
    7 4
    6 2
    7 5
    6 1
    1 3
    7 6
    10 2
    1 3
    5 4
    5 8
    5 9
    9 1
    2 5
    9 6
    1 10
    5 7
    (输出)
    #1 9
    #2 7

    1. public class 路径管理 {
    2.     private static final HashMap<Integer, LinkedList<Integer>> adj = new HashMap<>();
    3.     private static final LinkedList<Integer> stack = new LinkedList<>();
    4.     private static final long[] tree = new long[260_005];
    5.     private static int N, start, offset;
    7.     public static void main(String[] args) throws Exception {
    9.         StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    10.         in.nextToken();
    11.         int T = (int) in.nval;
    12.         for (int t = 1; t <= T; t++) {
    13.             in.nextToken();
    14.             N = (int) in.nval;
    15.             in.nextToken();
    16.             start = (int) in.nval;
    17.             Arrays.fill(tree, 0);
    18.             for (int i = 1; i < N; i++) {
    19.                 in.nextToken();
    20.                 int a = (int) in.nval;
    21.                 in.nextToken();
    22.                 int b = (int) in.nval;
    23.                 adj.computeIfAbsent(a, l -> new LinkedList<>()).add(b);
    24.             }
    25.             offset = 1;
    26.             while (offset < N)
    27.                 offset <<= 1;
    29.             offset--;
    30.             System.out.println("#" + t + " " + dfs());
    31.         }
    32.     }
    34.     private static long dfs() {
    35.         stack.add(start);
    36.         update(start, 1);
    37.         long sum = 0;
    38.         while (!stack.isEmpty()) {
    39.             LinkedList<Integer> next = adj.get(stack.peekLast());
    40.             if (next == null || next.isEmpty()) {
    41.                 int out = stack.pollLast();
    42.                 update(out, -1);
    43.             } else {
    44.                 int in = next.poll();
    45.                 sum += query(in + 1, N);
    46.                 stack.add(in);
    47.                 update(in, 1);
    48.             }
    49.         }
    50.         return sum;
    51.     }
    53.     private static void update(int i, int v) {
    54.         i = offset + i;
    55.         while (i > 0) {
    56.             tree[i] += v;
    57.             i >>= 1;
    58.         }
    60.     }
    62.     private static long query(int s, int e) {
    63.         long sum = 0;
    64.         s += offset;
    65.         e += offset;
    66.         while (s <= e) {
    67.             if (s % 2 == 1)
    68.                 sum += tree[s];
    69.             if (e % 2 == 0)
    70.                 sum += tree[e];
    71.             s = (s + 1) >> 1;
    72.             e = (e - 1) >> 1;
    73.         }
    74.         return sum;
    75.     }
    77. }