Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void solve() {
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- long a = scanner.nextInt();
- long b = scanner.nextInt();
- scanner.nextLine();
- // create tree
- int[] parents = new int[n];
- for (int i=1; i<n; i++) {
- int p = scanner.nextInt();
- scanner.nextLine();
- parents[i] = p;
- }
- // mark buyers for each node in tree
- int[] c = new int[n];
- for (int i=0; i<m; i++) {
- long v = (a * i + b) % n;
- c[(int) v]++;
- }
- long ans = 0;
- for (int i=n-1; i>=0; i--) {
- // find first grandparent which has buyers available (or possible root with 0 buyers)
- int gp = i;
- while (c[gp] == 0 && gp != 0) gp = parents[gp];
- // speedup future searches by marking this grandparent to all nodes within this path
- int curr = i;
- while (curr != gp) {
- int next = parents[curr];
- parents[curr] = gp;
- curr = next;
- }
- // if grandparent has buyers available, spend 1 buyer on candy i
- if (c[gp] > 0) {
- c[gp]--;
- ans += i;
- }
- }
- io.println(ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement