「美团CodeM复赛」城市网络 - 倍增

题目大意

    有一个树状的城市网络（即$n$个城市由$n-1$条道路连接的连通图），首都为$1$号城市，每个城市售卖价值为$a_i$的珠宝。
    你是一个珠宝商，现在安排有$q$次行程，每次行程为从$u$号城市前往$v$号城市（走最短路径），保证$v$在$u$前往首都的最短路径上。
    在每次行程开始时，你手上有价值为$c$的珠宝（每次行程可能不同），并且每经过一个城市时（包括$u$和$v$），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
    现在你想要对每一次行程，求出会进行多少次购买事件。

---

题目分析

询问是从指定点下方开始向上爬树，而不是图中原有的点，为了方便处理，我们新建一个点代表每个询问的开始结点，挂在指定点下方。

每个点都会跳到第一个比其权值大的点，一直跳到目标结点。
这个过程的目标确定，具有方向性，因此可以利用倍增优化。

假设已经得到了每个点第一个比其权值大的祖先结点，则可以预处理第$2^k$跳到的结点，在满足限制条件的情况下尽可能地向上倍增。

现在考虑如何找到比每个点大的第一个结点。
那么我们只需要在不比起始结点大的点中尽可能向上跳即可，这一步也可以用倍增实现。

因此本题用两次倍增完成。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=200005;
int n,q,a[maxn],p[maxn][25],Depth[maxn],Target[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Dfs(int Now,int fa) {
	int pos=fa;
	for(int i=log2(2*n); i>=0; i--)
		if(~p[pos][i]&&a[p[pos][i]]<=a[Now])pos=p[pos][i];
	if(a[pos]>a[Now])p[Now][0]=fa;
	else p[Now][0]=p[pos][0];
	for(int j=1; j<=log2(2*n); j++)
		if(~p[Now][j-1])p[Now][j]=p[p[Now][j-1]][j-1];
	Depth[Now]=Depth[fa]+1;
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		Dfs(Next,Now);
	}
}

int main() {
	memset(p,-1,sizeof(p));
	n=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
	}
	for(int i=1; i<=q; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		a[n+i]=v;
		AddEdge(n+i,x);
		AddEdge(x,n+i);
		Target[i]=y;
	}
	Dfs(1,-1);
	for(int i=1; i<=q; i++) {
		int ans=0,pos=n+i;
		for(int j=log2(2*n); j>=0; j--)
			if(~p[pos][j]&&Depth[p[pos][j]]>=Depth[Target[i]]) {
				ans^=1<<j;
				pos=p[pos][j];
			}
		printf("%d\n",ans);
	}
	return 0;
}