阿祁的部落格

CSES 1687 -  Company Queries I 解題心得( 題目 )

解題概念:tree 倍增表

解題方法:這題利用倍增表(Sparse table)，st[i][j]存i節點上的2^j的父節點，之後可使用O(logN)的複雜度查詢一筆資料，另外st[i][j]可使用DP的觀點求得。

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;

    }

}