求助,#2 #8 #9 #10 RE
查看原帖
求助,#2 #8 #9 #10 RE
862476
pineapplee楼主2023/3/8 20:00
import java.io.*;
import java.util.*;

public class Main{

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer in = new StringTokenizer("");
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static int[] tree;
    public static int n;
    public static int[] p;
    public static person[] ps;
    public static LinkedList<Integer>[] children;
    public static long[] ans;

    public static void main(String[] args) throws IOException{
        n = nextInt();
        p = new int[100001];
        ps = new person[n+1];
        tree = new int[n+1];
        children = new LinkedList[n+1];
        ans = new long[n+1];
        for (int i=1;i<=n;i++){
            children[i] = new LinkedList<>();
            ps[i] = new person(i,nextInt());
        }
        ps[0] = new person(0,0);
        //数据离散化
        Arrays.sort(ps, new Comparator<person>() {
            @Override
            public int compare(person o1, person o2) {
                return o1.p-o2.p;
            }
        });
        for (int i=1;i<=n;i++){
            p[ps[i].index] = i;
        }
        //建树
        for (int i=2;i<=n;i++){
            int f = nextInt();
            children[f].add(i);
        }
        dfs(1);
        for (int i=1;i<=n;i++)
            out.println(ans[i]);
        out.flush();
    }

    public static void dfs(int root){
        LinkedList<Integer> c = children[root];
        if(c.isEmpty())
            ans[root] = 0;
        else{
            ans[root] -= query(n) - query(p[root]);
            for (int i=0;i<c.size();i++){
                int child = c.get(i);
                dfs(child);
            }
            ans[root] += query(n)-query(p[root]);
        }
        add(p[root],1);
    }

    public static String next() throws IOException{
        while(!in.hasMoreTokens())
            in = new StringTokenizer(reader.readLine());
        return in.nextToken();
    }

    public static int nextInt() throws IOException{
        return Integer.valueOf(next());
    }


    public static void add(int i,int val){//添加元素
        for (;i<=n;i+=lowbit(i)){
            tree[i]+=val;
        }
    }
    public static long query(int i){
        long sum = 0;
        for (int j=i;j>0;j-=lowbit(j))
            sum+=tree[j];
        return sum;
    }

    public static int lowbit(int i){
        return i&(-i);
    }
}

class person{
    int index;
    int p;
    public person(int index, int p){
        this.index = index;
        this.p = p;
    }
}
2023/3/8 20:00
加载中...