JIH的玩偶

问题描述

JIH的玩具厂设立以来，发展了一张销售关系网。这张网以玩具厂为总代理（根），构成一颗树。每个节点都代表一个客户，且每个节点都有重要度ai。JIH想将这些客户划成若干类别，当然同一类的客户重要度相差太大总是不妥。所以JIH决定先进行市场调研。JIH会选择两个客户X，从X向根走一共k个节点进行调查。调查的结果是这条路径上重要程度相差最大的两个客户的差值是多少。因为特殊需要，要求重要度大的客户必须在重要度小的客户后面（顺序为X到根，若序列为递减，则输出0，详情见样例）。

输入

第一行一个整数N 表示N个客户
第二行N个整数Ai 表示N个客户的重要程度（工厂是1）
第三行开始 共N-1行 每行2个整数 x,y 表示x的父亲是y
接着一行一个正整数Q，表示Q次调研
接着Q行，每行两个整数X，K。含义见题目表述。

输出

Q行，每行一个正整数，含义见题目描述。

样例数据

Sample Input:

6
5 6 1 7 5 2
2 1
3 1
4 2
5 2
6 3
3
4 3
6 2
6 3

Sample Output:

0
0
4

数据范围

30% 的数据中N,Q<=1000
100%的数据中N,Q<=200000 Ai<=1000000

---

这是我有史以来最想吐槽的一道题，题目想表达什么都不知道。
老师说题意是，从x向根走一共k个节点中选两个，大的在小的后面，求最大相差多少。
姑且接受。

#include<iostream>
#include<cstdio>
using namespace std;
int mn[200005][18],mx[200005][18],h[200005][18],ans[200005][18];
int a[200005];
int head[200005],nxt[200005],vet[200005],num;
int n,q;
void addedge(int x,int y) {
	num++;
	vet[num]=y;
	nxt[num]=head[x];
	head[x]=num;
}
void dfs(int x,int fa) {
	if (fa>0) {
		int v=fa,tmp=0;
		h[x][0]=fa;
		mx[x][0]=max(a[x],a[fa]);
		mn[x][0]=min(a[x],a[fa]);
		if (a[x]<a[fa]) ans[x][0]=a[fa]-a[x];
		while (v>0) {
			h[x][tmp+1]=h[v][tmp];
			mx[x][tmp+1]=max(mx[x][tmp],mx[v][tmp]);
			mn[x][tmp+1]=min(mn[x][tmp],mn[v][tmp]);
			ans[x][tmp+1]=max(ans[x][tmp],max(ans[v][tmp],mx[v][tmp]-mn[x][tmp]));
			v=h[v][tmp];
			tmp++;
		}
	}
	for (int e=head[x];e!=0;e=nxt[e]) dfs(vet[e],x);
}
int main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin >> n;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(y,x);
	}
	dfs(1,0);
	cin >> q;
	while (q--) {
		int x,k;
		scanf("%d%d",&x,&k);
		k--;
		int mnn=1e9,anss=0;
		while (k>0) {
			int tmp=0;
			while ((k&(1<<tmp))==0) tmp++;
			k^=(1<<tmp);
			anss=max(anss,max(ans[x][tmp],mx[x][tmp]-mnn));
			mnn=min(mnn,mn[x][tmp]);
			x=h[x][tmp];
			if (x==0) break;
		}
		printf("%d\n",anss);
	}
	return 0;
}