UPC 1017 Easy Tree Query （二叉搜索树）

题目描述

You are given a binary search tree with depth k, whose nodes are valued from 1 to (2k − 1) and then Q queries.

For each query, you are given p nodes. Find the root of a smallest subtree which contains all p nodes and print its value.

输入

The first line of input contains an integer T (T ≤ 100), the number of test cases. The first line of each test case contains two integers k (1 ≤ k ≤ 60) and Q (1 ≤ Q ≤ 10 4 ). In next Q lines, each line contains an integer p and then p integers — the values of nodes in this query. It is guaranteed that the total number of nodes given in each test case will not exceed 105.

输出

For each query, print a line contains the answer of that query.

样例输入

1
4 1
3 10 15 13

样例输出

12

题意

在深度为 k 的二叉搜索树中，给出 q 次查询，输出每次查询节点的最近共同祖先。

思路

二叉搜索树有这样一个性质，即把树上所有节点从左到右依次输出其值刚好是排序的。

我们可以先对所要查询的点排序，设定 root 为当前判断的根节点。

1. 若 a[0]<=root&&a[n-1]>=root ，说明这些点遍布在 root 的两棵子树中，此时最近公共祖先便是 root 咯！
2. 若 a[0]>root ，说明所有节点都在 root 的右子树中，更新 root 为其右孩子节点，返回第一步。
3. 若 a[n-1]<root ，说明所有节点都在 root 的左子树中，更新 root 为其左孩子节点，返回第一步。

AC 代码

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <math.h>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <ctime>
#define INF 0x3f3f3f3f
#define MAXN 1000005
#define Mod 1000000007
using namespace std;

typedef unsigned long long LL;

LL a[MAXN];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int k,q;
        scanf("%d%d",&k,&q);
        while(q--)
        {
            int n;
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                scanf("%llu",a+i);
            sort(a,a+n);
            int t=k;
            LL root=(LL)1<<t;
            while(true)
            {
                if(a[0]<=root&&a[n-1]>=root)
                {
                    printf("%llu\n",root);
                    break;
                }
                if(a[n-1]<root)
                {
                    t--;
                    root-=(LL)1<<t;
                }
                else if(a[0]>root)
                {
                    t--;
                    root+=(LL)1<<t;
                }
            }
        }
    }
    return 0;
}