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

• 問題: No.650 行列木クエリ
• ユーザー: yuya178
• 提出日時: 2018-02-10 15:38:17
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 502 ms / 2,000 ms
• コード長: 13,321 bytes
• コンパイル時間: 2,775 ms
• コンパイル使用メモリ: 81,808 KB
• 実行使用メモリ: 70,488 KB
• 最終ジャッジ日時: 2024-04-21 15:27:00
• 合計ジャッジ時間: 6,887 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	92 ms; 40,028 KB
testcase_01	AC	312 ms; 49,728 KB
testcase_02	AC	469 ms; 70,488 KB
testcase_03	AC	96 ms; 40,080 KB
testcase_04	AC	314 ms; 49,472 KB
testcase_05	AC	483 ms; 68,344 KB
testcase_06	AC	91 ms; 39,844 KB
testcase_07	AC	90 ms; 38,484 KB
testcase_08	AC	359 ms; 50,372 KB
testcase_09	AC	502 ms; 69,076 KB
testcase_10	AC	88 ms; 39,828 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);
        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};
            tree.addEdge(a, b);
        }
        tree.init();
        SegmentTree[] seg = new SegmentTree[tree.getHeavyEdgeCount()];
        for (int i = 0; i < seg.length; i++) {
            seg[i] = new SegmentTree(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 = new long[]{1,0,0,1};
                while (true) {
                    int idx = tree.getIndexInHeavyEdge(v);
                    int left = ei == ej ? tree.getIndexInHeavyEdge(u) + 1 : 0;
                    long[] res = seg[ej].query(left, idx+1);
                    ans = comb(res, ans);
                    if (ej == ei) break;
                    v = tree.getParentVertex(ej);
                    ej = tree.getHeavyEdgeId(v);
                }
                out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
            } 
        }
    }

    long[] comb(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;
    }

    HeavyLightDecomposition tree;
    
    class SegmentTree {
        int n;
        long[][] seg;
        long[] id = new long[]{1,0,0,1};
        SegmentTree(int n) {
            this.n = Integer.highestOneBit(n) << 1;
            this.seg = new long[this.n<<1][];
            Arrays.fill(seg,id);
        }
        long[] comb(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;
        }
        void update(int x, long[] value) {
            x += n - 1;
            this.seg[x] = value;
            while (x > 0) {
                x = (x - 1) / 2;
                this.seg[x] = comb(this.seg[2 * x + 1], this.seg[2 * x + 2]);
            }
        }
        long[] query(int a,int b,int l,int r,int k){
            if(a<=l&&r<=b) return seg[k];
            if(b<=l||r<=a) return id;
            long[] ans1=query(a,b,l,(l+r)/2,2*k+1);
            long[] ans2=query(a,b,(l+r)/2,r,2*k+2);
            return comb(ans1, ans2);
        }
        long[] query(int l, int r) {
            return query(l,r,0,n,0);
        }
    }
    
    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)); }
 
}