Submit Info #32084

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum java dalt AC 2362 ms 201.58 MiB

ケース詳細
Name Status Time Memory
example_00 AC 63 ms 9.60 MiB
max_random_00 AC 2325 ms 201.43 MiB
max_random_01 AC 2195 ms 201.55 MiB
max_random_02 AC 2206 ms 201.27 MiB
max_random_03 AC 2362 ms 201.58 MiB
max_random_04 AC 2217 ms 201.41 MiB
random_00 AC 1636 ms 138.99 MiB
random_01 AC 1620 ms 141.98 MiB
random_02 AC 1104 ms 80.38 MiB
random_03 AC 913 ms 137.93 MiB
random_04 AC 894 ms 65.98 MiB
small_00 AC 89 ms 12.17 MiB
small_01 AC 88 ms 11.84 MiB
small_02 AC 98 ms 12.64 MiB
small_03 AC 87 ms 12.50 MiB
small_04 AC 111 ms 13.38 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.util.Arrays; import java.io.IOException; import java.io.UncheckedIOException; import java.io.Closeable; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); DynamicTreeSubtreeAddSubtreeSum solver = new DynamicTreeSubtreeAddSubtreeSum(); solver.solve(1, in, out); out.close(); } } static class DynamicTreeSubtreeAddSubtreeSum { public void solve(int testNumber, FastInput in, FastOutput out) { int n = in.readInt(); int q = in.readInt(); EulerTourTree ett = new EulerTourTree(n); for (int i = 0; i < n; i++) { ett.nodes[i].val = in.readInt(); ett.nodes[i].pushUp(); } for (int i = 0; i < n - 1; i++) { ett.link(in.readInt(), in.readInt()); } for (int i = 0; i < q; i++) { int t = in.readInt(); if (t == 0) { ett.cut(in.readInt(), in.readInt()); ett.link(in.readInt(), in.readInt()); } else if (t == 1) { int r = in.readInt(); int p = in.readInt(); ett.cut(r, p); EulerTourTree.Splay.splay(ett.nodes[r]); ett.nodes[r].modify(in.readInt()); ett.nodes[r].pushUp(); ett.link(r, p); } else { int v = in.readInt(); int p = in.readInt(); ett.cut(v, p); EulerTourTree.Splay.splay(ett.nodes[v]); out.println(ett.nodes[v].sum); ett.link(v, p); } } } } static class EulerTourTree { EulerTourTree.Splay[] nodes; LongObjectHashMap<EulerTourTree.Edge> map; public EulerTourTree(int n) { map = new LongObjectHashMap<>(n, true); nodes = new EulerTourTree.Splay[n]; for (int i = 0; i < n; i++) { nodes[i] = alloc(i); nodes[i].w = 1; nodes[i].pushUp(); } } private EulerTourTree.Splay alloc(int id) { EulerTourTree.Splay splay = new EulerTourTree.Splay();//buffer.alloc(); splay.id = id; return splay; } private void destroy(EulerTourTree.Splay s) { //buffer.release(s); } public int rootOf(int i) { return rootOf(nodes[i]).id; } public void setRoot(int i) { if (rootOf(i) == i) { return; } EulerTourTree.Splay.splay(nodes[i]); EulerTourTree.Splay l = EulerTourTree.Splay.splitLeft(nodes[i]); if (l == EulerTourTree.Splay.NIL) { return; } EulerTourTree.Splay a = EulerTourTree.Splay.selectMinAsRoot(l); EulerTourTree.Splay b = EulerTourTree.Splay.selectMaxAsRoot(nodes[i]); if (nodes[a.id] == a) { EulerTourTree.Splay.splitLeft(b); destroy(b); } else { l = EulerTourTree.Splay.splitRight(a); destroy(a); } EulerTourTree.Splay newNode = alloc(i); EulerTourTree.Splay.splay(nodes[i]); EulerTourTree.Splay.splay(l); EulerTourTree.Splay.merge(nodes[i], EulerTourTree.Splay.merge(l, newNode)); } private long idOfEdge(int i, int j) { if (i > j) { int tmp = i; i = j; j = tmp; } return (((long) i) << 32) | j; } public void link(int i, int j) { setRoot(i); setRoot(j); EulerTourTree.Edge e = new EulerTourTree.Edge(); long id = idOfEdge(i, j); e.a = alloc(-1); e.b = alloc(-1); map.put(id, e); EulerTourTree.Splay.splay(nodes[i]); EulerTourTree.Splay.splay(nodes[j]); EulerTourTree.Splay.merge(nodes[i], e.a); EulerTourTree.Splay.merge(nodes[j], e.b); EulerTourTree.Splay.splay(nodes[i]); EulerTourTree.Splay.splay(nodes[j]); EulerTourTree.Splay.merge(nodes[i], nodes[j]); EulerTourTree.Splay newNode = alloc(i); EulerTourTree.Splay.splay(nodes[i]); EulerTourTree.Splay.merge(nodes[i], newNode); } private EulerTourTree.Splay rootOf(EulerTourTree.Splay x) { EulerTourTree.Splay.splay(x); return EulerTourTree.Splay.selectMinAsRoot(x); } public void cut(int i, int j) { long id = idOfEdge(i, j); EulerTourTree.Edge e = map.remove(id); EulerTourTree.Splay.splay(e.a); EulerTourTree.Splay al = EulerTourTree.Splay.splitLeft(e.a); EulerTourTree.Splay ar = EulerTourTree.Splay.splitRight(e.a); EulerTourTree.Splay l, r; if (rootOf(ar) == rootOf(e.b)) { EulerTourTree.Splay.splay(e.b); EulerTourTree.Splay bl = EulerTourTree.Splay.splitLeft(e.b); EulerTourTree.Splay br = EulerTourTree.Splay.splitRight(e.b); l = al; r = br; } else { EulerTourTree.Splay.splay(e.b); EulerTourTree.Splay bl = EulerTourTree.Splay.splitLeft(e.b); EulerTourTree.Splay br = EulerTourTree.Splay.splitRight(e.b); l = bl; r = ar; } EulerTourTree.Splay.splay(l); EulerTourTree.Splay.splay(r); l = EulerTourTree.Splay.selectMaxAsRoot(l); r = EulerTourTree.Splay.selectMinAsRoot(r); if (nodes[l.id] == l) { EulerTourTree.Splay rSnapshot = r; r = EulerTourTree.Splay.splitRight(r); destroy(rSnapshot); } else { EulerTourTree.Splay lSnapshot = l; l = EulerTourTree.Splay.splitLeft(l); destroy(lSnapshot); } EulerTourTree.Splay.merge(l, r); destroy(e.a); destroy(e.b); } private static class Edge { EulerTourTree.Splay a; EulerTourTree.Splay b; } public static class Splay implements Cloneable { public static final EulerTourTree.Splay NIL = new EulerTourTree.Splay(); EulerTourTree.Splay left = NIL; EulerTourTree.Splay right = NIL; EulerTourTree.Splay father = NIL; int size; int id; long val; long sum; long dirty; int w; static { NIL.left = NIL; NIL.right = NIL; NIL.father = NIL; NIL.size = 0; NIL.id = -2; } public void modify(long x) { val += x; sum += x * size; dirty += x; } public static void splay(EulerTourTree.Splay x) { if (x == NIL) { return; } EulerTourTree.Splay y, z; while ((y = x.father) != NIL) { if ((z = y.father) == NIL) { y.pushDown(); x.pushDown(); if (x == y.left) { zig(x); } else { zag(x); } } else { z.pushDown(); y.pushDown(); x.pushDown(); if (x == y.left) { if (y == z.left) { zig(y); zig(x); } else { zig(x); zag(x); } } else { if (y == z.left) { zag(x); zig(x); } else { zag(y); zag(x); } } } } x.pushDown(); x.pushUp(); } public static void zig(EulerTourTree.Splay x) { EulerTourTree.Splay y = x.father; EulerTourTree.Splay z = y.father; EulerTourTree.Splay b = x.right; y.setLeft(b); x.setRight(y); z.changeChild(y, x); y.pushUp(); } public static void zag(EulerTourTree.Splay x) { EulerTourTree.Splay y = x.father; EulerTourTree.Splay z = y.father; EulerTourTree.Splay b = x.left; y.setRight(b); x.setLeft(y); z.changeChild(y, x); y.pushUp(); } public void setLeft(EulerTourTree.Splay x) { left = x; x.father = this; } public void setRight(EulerTourTree.Splay x) { right = x; x.father = this; } public void changeChild(EulerTourTree.Splay y, EulerTourTree.Splay x) { if (left == y) { setLeft(x); } else { setRight(x); } } public void pushUp() { if (this == NIL) { return; } size = left.size + right.size + w; sum = left.sum + val * w + right.sum; } public void pushDown() { if (dirty != 0) { left.modify(dirty); right.modify(dirty); dirty = 0; } } public static void toString(EulerTourTree.Splay root, StringBuilder builder) { if (root == NIL) { return; } root.pushDown(); toString(root.left, builder); builder.append(root.id).append(','); toString(root.right, builder); } public EulerTourTree.Splay clone() { try { return (EulerTourTree.Splay) super.clone(); } catch (CloneNotSupportedException e) { throw new RuntimeException(e); } } public static EulerTourTree.Splay cloneTree(EulerTourTree.Splay splay) { if (splay == NIL) { return NIL; } splay = splay.clone(); splay.left = cloneTree(splay.left); splay.right = cloneTree(splay.right); return splay; } public static EulerTourTree.Splay selectMinAsRoot(EulerTourTree.Splay root) { if (root == NIL) { return root; } root.pushDown(); while (root.left != NIL) { root = root.left; root.pushDown(); } splay(root); return root; } public static EulerTourTree.Splay selectMaxAsRoot(EulerTourTree.Splay root) { if (root == NIL) { return root; } root.pushDown(); while (root.right != NIL) { root = root.right; root.pushDown(); } splay(root); return root; } public static EulerTourTree.Splay splitLeft(EulerTourTree.Splay root) { root.pushDown(); EulerTourTree.Splay left = root.left; left.father = NIL; root.setLeft(NIL); root.pushUp(); return left; } public static EulerTourTree.Splay splitRight(EulerTourTree.Splay root) { root.pushDown(); EulerTourTree.Splay right = root.right; right.father = NIL; root.setRight(NIL); root.pushUp(); return right; } public static EulerTourTree.Splay merge(EulerTourTree.Splay a, EulerTourTree.Splay b) { if (a == NIL) { return b; } if (b == NIL) { return a; } a = selectMaxAsRoot(a); a.setRight(b); a.pushUp(); return a; } public String toString() { StringBuilder builder = new StringBuilder().append(id).append(":"); toString(cloneTree(this), builder); return builder.toString(); } } } static class Hasher { private long time = System.nanoTime() + System.currentTimeMillis() * 31L; public int shuffle(long z) { z += time; z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L; return (int) (((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32); } public int hash(long x) { return shuffle(x); } } static interface LongObjectEntryIterator<V> { boolean hasNext(); void next(); long getEntryKey(); V getEntryValue(); } static class LongObjectHashMap<V> { private int[] slot; private int[] next; private long[] keys; private Object[] values; private int alloc; private boolean[] removed; private int mask; private int size; private boolean rehash; private Hasher hasher = new Hasher(); private int[] version; private int now; private void access(int i) { if (version[i] != now) { slot[i] = 0; version[i] = now; } } public LongObjectHashMap(int cap, boolean rehash) { this.mask = (1 << (32 - Integer.numberOfLeadingZeros(cap - 1))) - 1; slot = new int[mask + 1]; version = new int[mask + 1]; next = new int[cap + 1]; keys = new long[cap + 1]; values = new Object[cap + 1]; removed = new boolean[cap + 1]; this.rehash = rehash; } private void doubleCapacity() { int newSize = Math.max(next.length + 10, next.length * 2); next = Arrays.copyOf(next, newSize); keys = Arrays.copyOf(keys, newSize); values = Arrays.copyOf(values, newSize); removed = Arrays.copyOf(removed, newSize); } private void rehash() { int[] newSlots = new int[Math.max(16, slot.length * 2)]; int[] newVersions = new int[newSlots.length]; int newMask = newSlots.length - 1; for (int i = 0; i < slot.length; i++) { access(i); if (slot[i] == 0) { continue; } int head = slot[i]; while (head != 0) { int n = next[head]; int s = hash(keys[head]) & newMask; next[head] = newSlots[s]; newSlots[s] = head; head = n; } } this.slot = newSlots; this.mask = newMask; this.version = newVersions; now = 0; } private void alloc() { alloc++; if (alloc >= next.length) { doubleCapacity(); } next[alloc] = 0; removed[alloc] = false; values[alloc] = null; size++; } private int hash(long x) { return hasher.hash(x); } public void put(long x, V y) { int h = hash(x); int s = h & mask; access(s); if (slot[s] == 0) { alloc(); slot[s] = alloc; keys[alloc] = x; values[alloc] = y; } else { int index = findIndexOrLastEntry(s, x); if (keys[index] != x) { alloc(); next[index] = alloc; keys[alloc] = x; values[alloc] = y; } else { values[index] = y; } } if (rehash && size >= slot.length) { rehash(); } } public V remove(long x) { int h = hash(x); int s = h & mask; access(s); if (slot[s] == 0) { return null; } int pre = 0; int index = slot[s]; while (keys[index] != x) { pre = index; if (next[index] != 0) { index = next[index]; } else { break; } } if (keys[index] != x) { return null; } if (slot[s] == index) { slot[s] = next[index]; } else { next[pre] = next[index]; } removed[index] = true; size--; return (V) values[index]; } private int findIndexOrLastEntry(int s, long x) { int iter = slot[s]; while (keys[iter] != x) { if (next[iter] != 0) { iter = next[iter]; } else { return iter; } } return iter; } public LongObjectEntryIterator<V> iterator() { return new LongObjectEntryIterator() { int index = 1; int readIndex = -1; public boolean hasNext() { while (index <= alloc && removed[index]) { index++; } return index <= alloc; } public long getEntryKey() { return keys[readIndex]; } public Object getEntryValue() { return values[readIndex]; } public void next() { if (!hasNext()) { throw new IllegalStateException(); } readIndex = index; index++; } }; } public String toString() { LongObjectEntryIterator<V> iterator = iterator(); StringBuilder builder = new StringBuilder("{"); while (iterator.hasNext()) { iterator.next(); builder.append(iterator.getEntryKey()).append("->").append(iterator.getEntryValue()).append(','); } if (builder.charAt(builder.length() - 1) == ',') { builder.setLength(builder.length() - 1); } builder.append('}'); return builder.toString(); } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } } static class FastOutput implements AutoCloseable, Closeable, Appendable { private static final int THRESHOLD = 1 << 13; private final Writer os; private StringBuilder cache = new StringBuilder(THRESHOLD * 2); public FastOutput append(CharSequence csq) { cache.append(csq); return this; } public FastOutput append(CharSequence csq, int start, int end) { cache.append(csq, start, end); return this; } private void afterWrite() { if (cache.length() < THRESHOLD) { return; } flush(); } public FastOutput(Writer os) { this.os = os; } public FastOutput(OutputStream os) { this(new OutputStreamWriter(os)); } public FastOutput append(char c) { cache.append(c); afterWrite(); return this; } public FastOutput append(long c) { cache.append(c); afterWrite(); return this; } public FastOutput append(String c) { cache.append(c); afterWrite(); return this; } public FastOutput println(long c) { return append(c).println(); } public FastOutput println() { return append(System.lineSeparator()); } public FastOutput flush() { try { os.append(cache); os.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { os.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } }