Submit Info #19378

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum java yding13 AC 1977 ms 49.59 MiB

ケース詳細
Name Status Time Memory
example_00 AC 54 ms 9.11 MiB
max_random_00 AC 1977 ms 49.11 MiB
max_random_01 AC 1961 ms 49.06 MiB
max_random_02 AC 1901 ms 46.76 MiB
max_random_03 AC 1925 ms 45.62 MiB
max_random_04 AC 1950 ms 49.09 MiB
random_00 AC 1742 ms 49.59 MiB
random_01 AC 1519 ms 39.70 MiB
random_02 AC 1513 ms 48.16 MiB
random_03 AC 797 ms 33.62 MiB
random_04 AC 1367 ms 46.25 MiB
small_00 AC 101 ms 11.11 MiB
small_01 AC 87 ms 11.57 MiB
small_02 AC 96 ms 10.93 MiB
small_03 AC 87 ms 11.56 MiB
small_04 AC 112 ms 14.11 MiB

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { public long[] virtualSum, sum, lazy, cancel; public int[] parent, left, right, virtualSize, size, stack; public boolean[] rev; public int top; public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); st.nextToken(); int n = (int) st.nval; st.nextToken(); int q = (int) st.nval; long[] value = new long[n]; for (int i = 0; i != n; ++i) { st.nextToken(); value[i] = (int) st.nval; } Main tree = new Main(value); for (int i = 0; i != n - 1; ++i) { st.nextToken(); int n1 = (int) st.nval; st.nextToken(); int n2 = (int) st.nval; tree.link(n1, n2); } for (int i = 0; i != q; ++i) { st.nextToken(); int op = (int) st.nval; switch (op) { case 0: st.nextToken(); int u = (int) st.nval; st.nextToken(); int v = (int) st.nval; st.nextToken(); int w = (int) st.nval; st.nextToken(); int x = (int) st.nval; tree.cut(u, v); tree.link(w, x); break; case 1: st.nextToken(); v = (int) st.nval; st.nextToken(); int p = (int) st.nval; st.nextToken(); x = (int) st.nval; tree.makeRoot(p); tree.subTreeAdd(v, x); break; case 2: st.nextToken(); v = (int) st.nval; st.nextToken(); p = (int) st.nval; tree.makeRoot(p); pw.println(tree.subTreeSum(v)); break; } } pw.flush(); } public Main(long[] value) { int n = value.length; this.parent = new int[n]; Arrays.fill(parent, -1); this.left = new int[n]; Arrays.fill(left, -1); this.right = new int[n]; Arrays.fill(right, -1); this.virtualSum = Arrays.copyOfRange(value, 0, n); this.sum = Arrays.copyOfRange(value, 0, n); this.virtualSize = new int[n]; Arrays.fill(virtualSize, 1); this.size = new int[n]; Arrays.fill(size, 1); this.lazy = new long[n]; this.cancel = new long[n]; this.stack = new int[n]; this.rev = new boolean[n]; this.top = 0; } public boolean root(int node) { return parent[node] == -1 || left[parent[node]] != node && right[parent[node]] != node; } public void access(int node) { for (int prev = -1, curr = node; curr != -1; prev = curr, curr = parent[curr]) { splay(curr); virtualSum[curr] += sum(right[curr]); virtualSize[curr] += size(right[curr]); propagate(right[curr] = prev); virtualSum[curr] -= sum(right[curr]); virtualSize[curr] -= size(right[curr]); fix(curr); } splay(node); } public void makeRoot(int node) { access(node); rev[node] = !rev[node]; } public int findRoot(int node) { access(node); while (left[node] != -1) node = left[node]; return node; } public void split(int x, int y) { makeRoot(x); access(y); } public void link(int node, int father) { makeRoot(node); if (node != findRoot(father)) { virtualSum[parent[node] = father] += sum[node]; virtualSize[father] += size[node]; cancel[node] = lazy[father]; fix(father); } } public long subTreeSum(int node) { access(node); return virtualSum[node]; } public void subTreeAdd(int node, int value) { int root; if ((root = findRoot(node)) != node) { int father = largest(left[node]); cut(node, father); update(node, value); link(node, father); makeRoot(root); } else update(node, value); } public int largest(int node) { while (right[node] != -1) node = right[node]; return node; } public void cut(int x, int y) { makeRoot(x); if (x == findRoot(y) && right[x] == -1 && parent[x] == y) { parent[x] = left[y] = -1; fix(y); } } public void splay(int node) { stack[top++] = node; for (int curr = node; !root(curr); curr = parent[curr]) stack[top++] = parent[curr]; while (top != 0) propagate(stack[--top]); while (!root(node)) { if (!root(parent[node])) rotate(left[parent[node]] == node ^ left[parent[parent[node]]] == parent[node] ? node : parent[node]); rotate(node); } fix(node); } public void rotate(int node) { int father = parent[node]; int grandFather = parent[father]; if (!root(father)) { if (left[grandFather] == father) left[grandFather] = node; else right[grandFather] = node; } if (grandFather != -1) cancel[node] = lazy[grandFather]; if (left[father] == node) { if (right[node] != -1) { propagate(right[node]); parent[right[node]] = father; cancel[right[node]] = lazy[father]; } left[father] = right[node]; right[node] = father; } else { if (left[node] != -1) { propagate(left[node]); parent[left[node]] = father; cancel[left[node]] = lazy[father]; } right[father] = left[node]; left[node] = father; } parent[node] = grandFather; parent[father] = node; cancel[father] = lazy[node]; fix(father); } public void propagate(int node) { if (node == -1) return; if (rev[node]) { rev[node] = false; if (left[node] != -1) rev[left[node]] = !rev[left[node]]; if (right[node] != -1) rev[right[node]] = !rev[right[node]]; Utils.swap4(left, right, node); } if (parent[node] == -1) return; update(node, lazy[parent[node]] - cancel[node]); cancel[node] = lazy[parent[node]]; } public void update(int node, long value) { virtualSum[node] += virtualSize[node] * value; sum[node] += size[node] * value; lazy[node] += value; } public int size(int node) { return node == -1 ? 0 : size[node]; } public long sum(int node) { return node == -1 ? 0 : sum[node]; } public void fix(int node) { propagate(left[node]); propagate(right[node]); sum[node] = sum(left[node]) + sum(right[node]) + virtualSum[node]; size[node] = size(left[node]) + size(right[node]) + virtualSize[node]; } } class Utils { public static final int INT_MAX = (int) 1e9; public static final long LONG_MAX = (int) 1e18; public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void swap2(int[] array, int i, int j) { array[i] = array[i] ^ array[j]; array[j] = array[i] ^ array[j]; array[i] = array[i] ^ array[j]; } public static void swap3(int[] array, int i, int j) { array[i] ^= array[j] ^ (array[j] ^= (array[i] ^ array[j])); } public static void swap4(int[] array1, int[] array2, int i) { array1[i] ^= array2[i] ^ (array2[i] ^= (array1[i] ^ array2[i])); } public static void swap(double[][] matrix, int r1, int r2) { double[] temp = matrix[r1]; matrix[r1] = matrix[r2]; matrix[r2] = temp; } public static void swap(double[] vector, int i, int j) { double temp = vector[i]; vector[i] = vector[j]; vector[j] = temp; } public static void swap(TwoDPoint[] point, int i, int j) { TwoDPoint temp = point[i]; point[i] = point[j]; point[j] = temp; } } class TwoDPoint { double x; double y; } class Tuple { int s; int t; int c; public Tuple(int s, int t, int c) { this.s = s; this.t = t; this.c = c; } }