题目

1128 - Greatest Parent

PDF (English)

Statistics

Forum

A tree is a connected graph with no cycles. In this problem you are given a rooted tree, where each node contains an integer value. And the value of a node is strictly greater than the value of its parent. Now you are given a node and an integer query. You
have to find the greatest possible parent of this node (may include the node itself), whose value if greater than or equal to the given query integer.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers
N (1 ≤ N ≤ 10⁵), q (1 ≤ q ≤ 50000) where
N denotes the number of nodes and q denotes the number of queries. The nodes are numbered from
0 to N-1.

Then there will be N-1 lines. The i^th (1 ≤ i < N)
line contains two integers p_i and s_i (0 ≤ p_i < i, 1 ≤ s_i < 2³¹).
p_i denotes the parent and s_i denotes the value of the
i^th node, respectively. Assume that the given tree is correct and follows the restrictions as stated. You can assume that the
0^th node is the root and its value is 1.

Each of the next q lines contains a query. Each query contains two integers:
k and v (1 ≤ k < N, 1 ≤ v ≤ s_k).

Output

For each case, print the case number in a line. Then for each query, print the index of the greatest parent of node
k with value greater than or equal to v. You can assume that a solution exists.

Note

Dataset is huge. Use faster I/O methods.

题解和知识预备

题目很简单，就是求最近公共祖先的裸题，还是先介绍下的好。

最小公共祖先（LCA）

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。

另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

这里给出一个LCA的例子：

对于T=<V,E>：V={1,2,3,4,5}，E={(1,2),(1,3),(3,4),(3,5)}

则有：

那么如何求解呢？下面介绍LCA离线算法 - Tarjan算法

LCA离线算法 - Tarjan算法

首先要了解这个算法的核心思想，那就是“空间换时间”。所应用到的搜索算法是深度优先遍历DFS，然后应用并查集来实现快速的查询访问。首先对整个树进行深度优先遍历，并在遍历的过程中不断地把一些目前可能查询到的并且结果相同的节点用并查集合并。伪代码

	LCA(u){
		Make-Set(u)
		ancestor[Find-Set(u)]=u
		对于u的每一个孩子v {
			LCA(v)
			Union(u)
			ancestor[Find-Set(u)]=u
		}
		checked[u]=true
		对于每个(u,v)属于P{
			if checked[v]=true
			then 回答u和v的最近公共祖先为 ancestor[Find-Set(v)]
		}
	}

代码示例

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int Maxn=100010;

int stk[Maxn],size;
int v[Maxn],p[Maxn],ans[Maxn];

struct QUE{
	int val,pos;
}que;

vector<QUE> q[Maxn];//Query List
vector<int> vec[Maxn];

int bsearch(int val){
	int l=1,r=size;
	while (l<=r){
		int mid=(l+r)/2;
		if (v[stk[mid]]>=val)r=mid-1;
		else l=mid+1;
	}
	return stk[r+1];
}

int dfs(int r){
	int i;
	stk[++size]=r;
	for (i=0;i<q[r].size();i++){
		ans[q[r][i].pos]=bsearch(q[r][i].val);
	}
	for (i=0;i<vec[r].size();i++){
		dfs(vec[r][i]);
	}
	size--;
}

void solve(int tt){
    int n,m,i,tnode;
    printf("Case %d:\n",tt);
    scanf(" %d %d",&n,&m);
    v[0]=1;
    for (i=0;i<n;i++){
        vec[i].clear();
        q[i].clear();
    }
    for (i=1;i<n;i++){
        scanf(" %d %d",&p[i],&v[i]);
        vec[p[i]].push_back(i);
    }
    for (i=0;i<m;i++){
        scanf(" %d %d",&tnode,&que.val);
        que.pos=i;
        q[tnode].push_back(que);
    }
    size=0;
    dfs(0);
    for (i=0;i<m;i++){
        printf("%d\n",ans[i]);
    }
}

int main(){
	int T,tt=0;
	scanf(" %d",&T);
	while (T--){
		solve(++tt);
	}
	return 0;
}