阿祁的部落格

CSES 1688 -  Company Queries II 解題心得( 題目 )

解題概念:LCA

解題方法:這題利用倍增表(Sparse table)，st[i][j]存i節點上的2^j的父節點，之後透過倍增表以及dfs拜訪順序，去尋找u節點的2^j祖先是否為另一節點v的祖先，我們紀錄入、出棧順序，假設A入<B入<B出<A出，那就可以說A是B的祖先。

註:這題似乎會卡java常數，把DFS遞迴改成用stack模擬才AC。

註2:後來發現這題也可以O(1)查詢，解法是把樹壓平，並且對編號依照規則重新編碼，之後化為RMQ問題，同樣利用倍增表可O(1)查詢。

Java參考程式碼(更好意見可留言於下方，謝謝!):

//Author:En Chi Tsung(欉恩祁)

//Date:2022/02/21

import java.io.*;

import java.util.*;

public class cses1687 {

    public static int ret,r;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static int[] fa=new int[200005];

    public static int[][] st=new int[200005][19];

    public static void main(String[] args) throws Exception{

        final int n=readint();

        final int q=readint();

        for(int i=2;i<=n;i++) {

            fa[i]=readint();

        }

        for(int x=2;x<=n;x++) {

            st[x][0]=fa[x];

            for(int i=1;i<=18;i++) {

                st[x][i]=st[st[x][i-1]][i-1];

            }

        }

        int x,k;

        for(int j=0;j<q;j++) {

            x=readint();

            k=readint();

            for(int i=(1<<18),id=18;i>0;i=i>>1,id--) {

                if((i&k)==i) {

                    x=st[x][id];

                    k^=i;

                }

            }

            if(x==0) {

                bw.write("-1\n");

            }

            else {

                bw.write(x+"\n");

            }

        }

        bw.flush();

    }

    

    public static int readint() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}