#235350 (Java21) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: yuya178
• 提出日時: 2018-02-10 15:16:49
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 483 ms / 2,000 ms
• コード長: 13,924 bytes
• コンパイル時間: 3,739 ms
• コンパイル使用メモリ: 87,888 KB
• 実行使用メモリ: 70,472 KB
• 最終ジャッジ日時: 2024-10-13 13:06:35
• 合計ジャッジ時間: 6,379 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	94 ms; 40,156 KB
testcase_01	AC	298 ms; 48,652 KB
testcase_02	AC	452 ms; 68,388 KB
testcase_03	AC	106 ms; 39,972 KB
testcase_04	AC	301 ms; 48,904 KB
testcase_05	AC	444 ms; 66,908 KB
testcase_06	AC	99 ms; 39,948 KB
testcase_07	AC	98 ms; 40,076 KB
testcase_08	AC	338 ms; 50,200 KB
testcase_09	AC	483 ms; 70,472 KB
testcase_10	AC	98 ms; 40,084 KB

ソースコード

import java.io.*;
import java.util.*;
import java.math.*;
// import java.awt.Point;
 
public class Main {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
 
    static long mod = 1_000_000_007;
    int inf = Integer.MAX_VALUE;

    void solve(){
        int n = ni();
        tree = new HeavyLightDecomposition(n);
        // UnionFind uf = new UnionFind(n);
        int[][] es = new int[n-1][];
        for (int i = 0; i < n - 1; i++) {
            int a = ni();
            int b = ni();
            es[i] = new int[]{a,b};
            // uf.union(a, b);
            tree.addEdge(a, b);
        }
        tree.init();
        seg = new Seg2[tree.getHeavyEdgeCount()];
        for (int i = 0; i < seg.length; i++) {
            seg[i] = new Seg2(tree.getHeavyEdgeLength(i));
        }
        
        for (int[] e : es) {
            if (tree.g.childSize[e[0]] < tree.g.childSize[e[1]]) {
                int tmp = e[0];
                e[0] = e[1];
                e[1] = tmp;
            }
        }
        
        int q = ni();
        while (q-- > 0) {
            char c = nc();
            if (c == 'x') {
                int i = ni();
                int x00 = ni();
                int x01 = ni();
                int x10 = ni();
                int x11 = ni();
                int e = tree.getHeavyEdgeId(es[i][1]);
                int j = tree.getIndexInHeavyEdge(es[i][1]);
                seg[e].update(j, new long[]{x00,x01,x10,x11});
                
            } else if (c == 'g') {
                int u = ni();
                int v = ni();

                int ei = tree.getHeavyEdgeId(u);
                int ej = tree.getHeavyEdgeId(v);
                long[] ans = Seg2.id.clone();
                while (true) {
                    int idx = tree.getIndexInHeavyEdge(v);
                    int left = ei == ej ? tree.getIndexInHeavyEdge(u) + 1 : 0;
                    ans = Seg2.merge(seg[ej].get(left, idx + 1), ans);
                    if (ej == ei) break;
                    v = tree.getParentVertex(ej);
                    ej = tree.getHeavyEdgeId(v);
                }
                out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
            } 
        }
    }

    HeavyLightDecomposition tree;
    Seg2[] seg;
    
    static class Seg2 {
        final int n;
        final long[][] seg;
        
        public Seg2(final int n) {
            this.n = Integer.highestOneBit(n) << 1;
            seg = new long[this.n << 1][];
            Arrays.fill(seg, id);
        }
        
        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,};
        long[] get(int l, int r) { return get(l, r, 0, 0, n); }
        long[] get(int l, int r, int k, int curL, int curR) {
            if(curR <= l || curL >= r) return id;
            if(l <= curL && curR <= r) { return seg[k]; }
            final int curM = (curL + curR) / 2;
            return merge(
                    get(l, r, 2 * k + 1, curL, curM),
                    get(l, r, 2 * k + 2, curM, curR));
        }
        
        void update(int i, long[] v) {
            i += n - 1;
            seg[i] = v;
            while(i != 0) {
                i = (i - 1) / 2;
                seg[i] = merge(seg[2*i+1], seg[2*i+2]);
            }
        }
    }

    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)]; }
    }
    
    static public class HeavyLightDecomposition {
        final AdjListGraph g;
        
        public HeavyLightDecomposition(final int V) {
            g = new AdjListGraph(V, 2 * (V - 1));
        }
        
        void addEdge(int s, int t) {
            g.addEdge(s, t);
            g.addEdge(t, s);
        }
        
        int getHeavyEdgeCount() {
            return g.heavyEdgeCount;
        }
        
        int getHeavyEdgeLength(int heavyEdgeId) {
            return g.heavyEdge[heavyEdgeId].length;
        }
        
        int getHeavyEdgeDepth(int heavyEdgeId) {
            return g.heavyEdgeDepth[heavyEdgeId];
        }
        
        int getHeavyEdgeId(int vertexIndex) {
            return g.belongHeavyEdgeIndex[vertexIndex];
        }
        
        int getIndexInHeavyEdge(int vertexIndex) {
            return g.heavyEdgeIndex[vertexIndex];
        }
        
        int getParentVertex(int heavyEdgeId) {
            return g.heavyEdgeParent[g.heavyEdge[heavyEdgeId][0]];
        }
        
        void init() {
            g.initHeavyLightDecomposition();
        }
        
        static
        class AdjListGraph {
            int m, V, E;
            int[] head, next, to, childSize, parent;
            int[] heavyEdgeIndex;
            int[] belongHeavyEdgeIndex;
            int[] heavyEdgeParent;
            int[][] heavyEdge;
            int[] heavyEdgeVertexCount;
            int[] heavyEdgeDepth;
            int heavyEdgeCount;

            boolean[] vis;
            int[] st;
            
            public AdjListGraph(int V, int E) {
                head = new int[V];
                childSize = new int[V];
                heavyEdgeIndex = new int[V];
                belongHeavyEdgeIndex = new int[V];
                heavyEdgeVertexCount = new int[V];
                heavyEdgeDepth = new int[V];
                heavyEdgeParent = new int[V];
                parent = new int[V];
                next = new int[E];
                to = new int[E];
                vis = new boolean[head.length];
                st = new int[head.length + 1];
                this.V = V;
                this.E = E;
                clear();
            }
            
            public void clear() {
                m = 0;
                Arrays.fill(head, -1);
            }

            public void addEdge(int s, int t) {
                next[m] = head[s];
                head[s] = m;
                to[m++] = t;
            }

            public void initHeavyLightDecomposition() {
                calcChildSize(0);
                initHeavyEdge(0);
            }
            
            private void calcChildSize(final int root) {
                int sp = 0;

                parent[root] = -1;
                st[sp++] = root;
                while(sp != 0) {
                    final int v = st[--sp];
                    if(!vis[v]) {
                        st[sp++] = v;
                        childSize[v]++;
                        vis[v] = true;
                        for(int e = head[v]; e != -1; e = next[e]) {
                            final int u = to[e];
                            if(!vis[u]) {
                                parent[u] = v;
                                st[sp++] = u;
                            }
                        }
                    }
                    else if(parent[v] != -1) {
                        childSize[parent[v]] += childSize[v];
                    }
                }
            }

            private void initHeavyEdge(final int root) {
                int sp = 0;
                st[sp++] = root;
                Arrays.fill(vis, false);
                heavyEdgeIndex[root] = 0;
                belongHeavyEdgeIndex[root] = heavyEdgeCount++;
                heavyEdgeParent[root] = -1;
                while(sp != 0) {
                    final int v = st[--sp];
                    if(!vis[v]) {
                        st[sp++] = v;
                        vis[v] = true;

                        heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]++;
//                      System.err.println(belongHeavyEdgeIndex[v] + " " + heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]);

                        int maxChildIndex = -1;
                        int maxChildSize = 0;
                        for(int e = head[v]; e != -1; e = next[e]) {
                            final int u = to[e];
                            if(!vis[u]) {
                                if(maxChildSize < childSize[u]) {
                                    maxChildIndex = u;
                                    maxChildSize = childSize[u];
                                }
//                              System.err.println(v + " -> " + u + " " + maxChildIndex);
                                st[sp++] = u;
                            }
                        }
                        

                        for(int e = head[v]; e != -1; e = next[e]) {
                            final int u = to[e];
                            if(!vis[u] && maxChildIndex != u) {
                                heavyEdgeIndex[u] = 0;
                                heavyEdgeDepth[heavyEdgeCount] = heavyEdgeDepth[belongHeavyEdgeIndex[v]] + 1;
//                              heavyEdgeVertexCount[heavyEdgeCount] = 1;
                                belongHeavyEdgeIndex[u] = heavyEdgeCount++;
                                heavyEdgeParent[u] = v;
                            }
                        }
                        
                        if(maxChildIndex != -1) {
                            heavyEdgeIndex[maxChildIndex] = heavyEdgeIndex[v] + 1;
                            belongHeavyEdgeIndex[maxChildIndex] = belongHeavyEdgeIndex[v];
                            heavyEdgeParent[maxChildIndex] = heavyEdgeParent[v];
                        }
                    }
                }
                
                heavyEdge = new int[heavyEdgeCount][];
                for(int i = 0; i < heavyEdgeCount; i++) {
                    heavyEdge[i] = new int[heavyEdgeVertexCount[i]];
                }
                
                for(int i = 0; i < V; i++) {
                    final int j = belongHeavyEdgeIndex[i];
//                  System.err.println(i + " " + j + " " + heavyEdgeIndex[i] + " " + heavyEdge[j].length);
                    heavyEdge[j][heavyEdgeIndex[i]] = i;
                }
            }
        }
    }

    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new Main().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b) && b != ' ')){
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
 
}