結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2017-04-09 13:05:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,751 ms / 2,000 ms |
コード長 | 9,001 bytes |
コンパイル時間 | 4,817 ms |
コンパイル使用メモリ | 86,528 KB |
実行使用メモリ | 119,692 KB |
最終ジャッジ日時 | 2024-12-20 10:03:30 |
合計ジャッジ時間 | 13,304 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
import java.io.*;import java.util.*;public class _p1317_Validate {public static void main(String[] args) throws IOException {new _p1317_Validate().solve();}static int mod = (int)1e9+7;void solve() throws IOException {try (final InputValidator in = new InputValidator(System.in)) {int n = in.nextInt(1, 100000);LinkCutTree[] tree = new LinkCutTree[n];g = new List[n];for (int i = 0; i < n; i++) {tree[i] = new LinkCutTree(i);g[i] = new ArrayList<>();}in.newLine();UnionFind uf = new UnionFind(n);int[][] es = new int[n-1][];for (int i = 0; i < n - 1; i++) {int a = in.nextInt(0, n - 1);in.space();int b = in.nextInt(0, n - 1);in.newLine();es[i] = new int[]{a,b};uf.union(a, b);g[a].add(b);g[b].add(a);}par = new int[n];init(0);for (int[] e : es) {if (par[e[0]] == e[1]) {int tmp = e[0];e[0] = e[1];e[1] = tmp;}tree[e[1]].link(tree[e[0]]);}int q = in.nextInt(1, 20000);in.newLine();while (q-- > 0) {char c = in.nextChar();in.space();if (c == 'x') {int i = in.nextInt(0, n - 2); in.space();int x00 = in.nextInt(0, 1000); in.space();int x01 = in.nextInt(0, 1000); in.space();int x10 = in.nextInt(0, 1000); in.space();int x11 = in.nextInt(0, 1000); in.newLine();tree[es[i][1]].set(new long[]{x00,x01,x10,x11});} else if (c == 'g') {int u = in.nextInt(0, n - 1); in.space();int v = in.nextInt(0, n - 1); in.newLine();long[] tmp = tree[u].value;tree[u].expose();tree[u].cut();tree[u].set(id);tree[v].expose();long[] ans = tree[v].sum;System.out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);tree[u].set(tmp);if (par[u] >= 0) {tree[u].link(tree[par[u]]);}} else {throw new RuntimeException();}}in.eof();}}void debug(LinkCutTree t, String path) {if (t != null) {debug(t.left, path + "L");dump(t.value, t.sum, t.index, path);debug(t.right, path + "R");}}List<Integer>[] g;int[] par;void init(int root) {int[] st = new int[g.length];int sp = 0;st[sp++] = root;par[root] = -1;// dump("par", v, p);while (sp != 0) {int v = st[--sp];for (int t : g[v]) if (t != par[v]) {st[sp++] = t;par[t] = v;}}}static long[] merge(long[] l, long[] r) {long[] res = new long[4];res[0] = (l[0] * r[0] + l[1] * r[2]) % mod;res[1] = (l[0] * r[1] + l[1] * r[3]) % mod;res[2] = (l[2] * r[0] + l[3] * r[2]) % mod;res[3] = (l[2] * r[1] + l[3] * r[3]) % mod;return res;}final static long[] id = new long[]{1,0,0,1,};static class LinkCutTree {LinkCutTree parent;LinkCutTree left;LinkCutTree right;boolean rev;long[] value;long[] sum;final int index;void debug() {dump(value, sum, index);}boolean isSplayRoot() {return parent == null ||parent.left != this && parent.right != this;}public LinkCutTree(final int index) {this.index = index;this.value = id;this.sum = id;}public void set(long[] value) {expose();this.value = value;update();}/*** expose後はrightは必ずnullなので単にsumを返すだけでよい。*/public long[] sum() {expose();return sum;}private void update() {sum = value;if (left != null) sum = merge(left.sum, sum);if (right != null) sum = merge(sum, right.sum);}public static LinkCutTree lca(LinkCutTree u, LinkCutTree v) {if(u == v) return u;LinkCutTree a = u.findRoot();LinkCutTree b = v.findRoot();if(a != b) {return null;}u.splay();if(u.parent != null && u.parent.left != u && u.parent.right != u) {return u.parent;}return u;}public void evert() {expose();rev = !rev;}/*** thisから根までのパスがsplay treeの形で構成されている状態になる* leftはthisの親* rightは必ずnull* なので、自分より根から遠いノードは存在しない*/private void expose() {LinkCutTree x = this;LinkCutTree r = null;for(LinkCutTree p = x; p != null; p = p.parent) {p.splay();p.right = r;r = p;}x.splay();}public LinkCutTree findRoot() {LinkCutTree v = this;v.expose();while(v.left != null)v = v.left;v.splay();return v;}public void cut() {expose();if (left == null) return;LinkCutTree p = left;left = null;p.parent = null;// while (p.right != null) p = p.right;update();p.splay();}public void link(LinkCutTree p) {if (p == null) return;expose();p.expose();parent = p;p.right = this;p.update();}static void rotateRight(LinkCutTree x) {final LinkCutTree p = x.parent;final LinkCutTree g = p.parent;p.left = x.right;if(x.right != null) { x.right.parent = p; }p.parent = x;x.right = p;x.parent = g;p.update();x.update();if(g != null) {if(g.left == p) g.left = x;else if(g.right == p) g.right = x;g.update();}}static void rotateLeft(LinkCutTree x) {final LinkCutTree p = x.parent;final LinkCutTree g = p.parent;p.right = x.left;if(x.left != null) { x.left.parent = p; }p.parent = x;x.left = p;x.parent = g;p.update();x.update();if(g != null) {if(g.left == p) g.left = x;else if(g.right == p) g.right = x;g.update();}}private void pushDown() {if (rev) {LinkCutTree t = left; left = right; right = t;if (left != null) left.rev = !left.rev;if (right != null) right.rev = !right.rev;rev = false;}}protected void splay() {final LinkCutTree x = this;while(!x.isSplayRoot()) {final LinkCutTree p = x.parent;if(p.isSplayRoot()) {p.pushDown();x.pushDown();// zig stepif(p.left == x) { rotateRight(x); }else { rotateLeft(x); }}else {final LinkCutTree g = p.parent;g.pushDown();p.pushDown();x.pushDown();// zig-zig step / zig-zag stepif(g.left == p) {if(p.left == x) { rotateRight(p); rotateRight(x); }else { rotateLeft(x); rotateRight(x); }}else {if(p.left == x) { rotateRight(x); rotateLeft(x); }else { rotateLeft(p); rotateLeft(x); }}}}}}static class UnionFind {private int[] data;public UnionFind(int size) {data = new int[size];clear();}public void clear() {Arrays.fill(data, -1);}public int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); }public void union(int x, int y) {if((x = root(x)) == (y = root(y))) {throw new RuntimeException();}if(data[y] < data[x]) { final int t = x; x = y; y = t; }data[x] += data[y];data[y] = x;}public boolean same(int x, int y) { return root(x) == root(y); }public int size(int x) { return -data[root(x)]; }}// for debugstatic void dump(Object... o) {System.err.println(Arrays.deepToString(o));}static class InputValidator implements Closeable {final InputStream in;final int NO_BUFFER = -2;int buffer;public InputValidator(final InputStream in) {this.in = in;buffer = NO_BUFFER;}public char nextChar() throws IOException {int res = read();check(Character.isLetterOrDigit(res));return (char)res;}int read() throws IOException {final int res = buffer == NO_BUFFER ? in.read() : buffer;buffer = NO_BUFFER;return res;}void unread(int ch) throws IOException {buffer = ch;}// [low, high]long nextLong(long low, long high) throws IOException {long val = 0;int ch = -1;boolean read = false;while (true) {ch = read();if (!Character.isDigit(ch)) break;read = true;val = val * 10 + ch - '0';check(val <= high);}check(read);check(ch >= 0);check(val >= low);unread(ch);return val;}int nextInt(int low, int high) throws IOException { return (int)nextLong(low, high); }int[] nextInts(int n, int low, int high) throws IOException {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt(low, high);if (i + 1 != n) space();}newLineOrEOF();return res;}void space() throws IOException { int ch = read(); check(ch == ' '); }void newLine() throws IOException {int ch = read();if (ch == '\r') ch = read();check(ch == '\n');}void newLineOrEOF() throws IOException { int ch = read(); check(ch == '\r' || ch == '\n' || ch < 0); }void eof() throws IOException { int ch = read(); check(ch < 0); }void check(boolean b) { if (!b) throw new RuntimeException(); }@Overridepublic void close() throws IOException {}}}