Submit Info #19600

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

ケース詳細
Name Status Time Memory
example_00 AC 59 ms 9.27 MiB
max_random_00 AC 2550 ms 61.61 MiB
max_random_01 AC 2527 ms 63.45 MiB
max_random_02 AC 2561 ms 62.87 MiB
max_random_03 AC 2673 ms 63.57 MiB
max_random_04 AC 2679 ms 63.66 MiB
random_00 AC 1931 ms 53.81 MiB
random_01 AC 2446 ms 57.67 MiB
random_02 AC 1552 ms 44.99 MiB
random_03 AC 1208 ms 49.35 MiB
random_04 AC 1626 ms 42.24 MiB
small_00 AC 99 ms 12.81 MiB
small_01 AC 85 ms 10.87 MiB
small_02 AC 97 ms 11.46 MiB
small_03 AC 93 ms 10.93 MiB
small_04 AC 98 ms 12.76 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[] value, pathSum, lazyPath, cancelPath, virtualSum, sum, lazySubTree, cancelSubTree; public int[] parent, left, right, pathSize, 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.value = value; pathSum = new long[n]; lazyPath = new long[n]; cancelPath = new long[n]; pathSize = new int[n]; virtualSum = Arrays.copyOf(value, n); sum = new long[n]; virtualSize = new int[n]; Arrays.fill(virtualSize, 1); size = new int[n]; lazySubTree = new long[n]; cancelSubTree = new long[n]; parent = new int[n]; Arrays.fill(parent, -1); left = new int[n]; Arrays.fill(left, -1); right = new int[n]; Arrays.fill(right, -1); stack = new int[n]; rev = new boolean[n]; top = 0; } public boolean root(int node) { return parent[node] == -1 || splayRoot(node); } public boolean splayRoot(int node) { return 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); if (right[curr] != -1) addVirtual(curr, right[curr]); if ((right[curr] = prev) != -1) { propagateSubTree(prev); cancelPath[prev] = lazyPath[curr]; removeVirtual(curr, 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) { if (commonRoot(node, father) != -1) return; cancel(node, father); addVirtual(father, node); fix(father); } public void rawLink(int node, int father) { makeRoot(node); cancel(node, father); addVirtual(father, node); fix(father); } public void cut(int x, int y) { if (commonRoot(x, y) != -1 && right[x] == -1 && parent[x] == y) { parent[x] = left[y] = -1; fix(y); } } public void rawCut(int x, int y) { split(x, y); parent[x] = left[y] = -1; fix(y); } public long subTreeSum(int node) { access(node); return virtualSum[node]; } public void subTreeAdd(int node, long value) { int root; if ((root = findRoot(node)) != node) { int father = father(left[node]); rawCut(node, father); updateSubTree(node, value); rawLink(node, father); makeRoot(root); } else updateSubTree(node, value); this.value[node] += value; } public int father(int node) { while (!largest(node)) node = right[node]; return node; } public boolean largest(int node) { flip(node); return right[node] == -1; } public long pathSum(int x, int y) { int root; if ((root = commonRoot(x, y)) == -1) return 0; long result = pathSum[y]; makeRoot(root); return result; } public void pathAdd(int x, int y, long value) { int root; if ((root = commonRoot(x, y)) == -1) return; updatePath(y, value); virtualSum[y] += value; makeRoot(root); } public int commonRoot(int x, int y) { int root = findRoot(x); rev[x] = !rev[x]; return x == findRoot(y) ? root : -1; } public void splay(int node) { stack[top++] = node; for (int curr = node; !root(curr); curr = parent[curr]) stack[top++] = parent[curr]; flip(stack[--top]); if (parent[stack[top]] != -1) propagateSubTree(stack[top]); while (top != 0) { flip(stack[--top]); 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 (parent[father] == -1) parent[node] = -1; else { cancel(node, grandFather); if (!splayRoot(father)) { if (left[grandFather] == father) left[grandFather] = node; else right[grandFather] = node; cancel(node, grandFather); } } if (left[father] == node) { if (right[node] != -1) { propagate(right[node]); cancel(right[node], father); } left[father] = right[node]; right[node] = father; } else { if (left[node] != -1) { propagate(left[node]); cancel(left[node], father); } right[father] = left[node]; left[node] = father; } cancel(father, node); fix(father); } public void cancel(int node, int father) { parent[node] = father; cancelPath[node] = lazyPath[father]; cancelSubTree[node] = lazySubTree[father]; } public void flip(int node) { 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); } } public void propagate(int node) { propagatePath(node); propagateSubTree(node); } public void propagatePath(int node) { long value = lazyPath[parent[node]] - cancelPath[node]; long pathAdd = pathSize[node] * value; pathSum[node] += pathAdd; updatePath(node, value); cancelPath[node] = lazyPath[parent[node]]; virtualSum[node] += value; sum[node] += pathAdd; } public void propagateSubTree(int node) { long value = lazySubTree[parent[node]] - cancelSubTree[node]; updateSubTree(node, value); sum[node] += size[node] * value; cancelSubTree[node] = lazySubTree[parent[node]]; pathSum[node] += pathSize[node] * value; this.value[node] += value; } public void updatePath(int node, long value) { this.value[node] += value; lazyPath[node] += value; } public void addVirtual(int father, int node) { virtualSum[father] += sum[node]; virtualSize[father] += size[node]; } public void removeVirtual(int father, int node) { virtualSum[father] -= sum[node]; virtualSize[father] -= size[node]; } public void updateSubTree(int node, long value) { virtualSum[node] += virtualSize[node] * value; lazySubTree[node] += value; } public long pathSum(int node) { return node == -1 ? 0 : pathSum[node]; } public long sum(int node) { return node == -1 ? 0 : sum[node]; } public int pathSize(int node) { return node == -1 ? 0 : pathSize[node]; } public int size(int node) { return node == -1 ? 0 : size[node]; } public void fix(int node) { if (left[node] != -1) propagate(left[node]); if (right[node] != -1) propagate(right[node]); sum[node] = sum(left[node]) + sum(right[node]) + virtualSum[node]; size[node] = size(left[node]) + size(right[node]) + virtualSize[node]; pathSum[node] = pathSum(left[node]) + pathSum(right[node]) + value[node]; pathSize[node] = pathSize(left[node]) + pathSize(right[node]) + 1; } } 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; } }