题目链接：https://ac.nowcoder.com/acm/problem/13331
来份在线查询的代码，先说这道题，在第一遍dfs求重儿子的时候，顺便处理数组dp[maxn]，其中dp[u]为从节点u到根节点1有几次购买操作，如何求答案呢？
假设有两个点x和y，其中y----是x的某一级祖先，而且y的值是从x到根节点路径上第一个比x大的节点，很显然，dp[x]=dp[y]+1。可以配合线段树维护实现查询第一个比x大的节点位置的操作。
本题目查询节点u和v，其中v保证是u的祖先节点。
对于u到v的路径上，我们找到第一个要购买操作的节点位置------假设为u1。
对于u到v的路径上，我们找到最后一个要购买操作的节点位置------假设为v1。
对于这条路径u---> u1(第一次购买操作) ---> v1(最后一次购买操作) ---> v
当然，存在u和u1是同一个位置这种类似情况，就是u和u1和v1和v不一定是不同的点，对我们的解题不构成影响
我们可以发现，u1肯定是第一个比出发是所携带的价值c大的节点，v1肯定是路径u->v中值最大且最靠近u的，因为第一次遇到就换，这很显然。
所以，起点到节点u1无操作，节点v1到v无操作，因此这两段路径我们可以不管，那么答案就是dp[u1]-dp[v1]+1，这就解决了。
所以，我们可以先树剖，然后线段树维护区间最值，深度越大越优先，并且设置id标记，标记最大值的下标，方便我们定位到符合要求的节点，对于查询u到v，找出u1和v1即可，2个查询函数就行。
重头戏来了，这题有个限制——v是u的祖先，很多人和我想法一定一样，不满足只解决有这个限制的题目，对于没有这个限制的题目，这种情况我们怎么解决，上面的方法还是可以进一步解决这个问题，我们已经用一个数组dp，对于dp[idx]表示了idx节点到根的路径上的操作次数。
我们可以增加一个数组rev_dp[maxn]，rev_dp[idx]维护的是对于从根节点走到节点idx的购买操作次数，和dp数组正好相反，怎么求呢，我们看啊，假设两个节点x和y，y是x的祖先且y是根节点到x节点路径的最大值且最靠近根节点，那么rev_dp[x]=rev_dp[y]+( val[x] > val[y] ? 1:0 )
我们可以先处理节点u到lca(u,v)的答案，保存了最大值MAX，得到sum1，和本题一样的处理得到的答案，再处理lca(u,v)到v的路径，我们只需要找到lca(u,v)到v路径的第一个值比MAX大的节点k1,以及路径中值最大且离v最远的节点k2，得到sum2=rev_dp[k2]-rev_dp[k1]+1,
答案就是sum1+sum2，这是大概思路，细节用线段树维护即可实现。
处理路径的时候用树剖，复杂度也满足要求。
这里给出思路，代码是解决该题的代码。
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define PI 3.1415926535898
using namespace std;
const int maxn=1e5+10;
struct edge {
int to,Next;
}Edge[maxn<<1];
int f[maxn],val[maxn],Son[maxn],Top[maxn],sz[maxn],dep[maxn],Head[maxn],tot,dp[maxn];
void Add(int from, int to) {
Edge[tot]={to,Head[from]};
Head[from]=tot++;
Edge[tot]={from,Head[to]};
Head[to]=tot++;
}
struct node {
int Left,Right,val,id;
}NODE[maxn<<2];
int pos[maxn];
void PushUp(int idx) {
NODE[idx].val=max(NODE[idx<<1].val,NODE[idx<<1|1].val);
if (NODE[idx].val==NODE[idx<<1|1].val) NODE[idx].id=NODE[idx<<1|1].id;
else NODE[idx].id=NODE[idx<<1].id;
}
void build(int l, int r, int idx) {
NODE[idx].Left=l,NODE[idx].Right=r;
NODE[idx].val=0;
if (l==r) {
NODE[idx].val=val[pos[l]];
NODE[idx].id=l;
return;
}
int m=(l+r)>>1;
build(l,m,idx<<1);
build(m+1,r,idx<<1|1);
PushUp(idx);
}
void Updata(int pos, int idx, int c) {
if (NODE[idx].Left==NODE[idx].Right) {
NODE[idx].val+=c;
return;
}
int m=(NODE[idx].Left+NODE[idx].Right)>>1;
if (pos<=m) Updata(pos,idx<<1,c);
else Updata(pos,idx<<1|1,c);
PushUp(idx);
}
int query_Max(int l, int r, int idx, int c) {
if (l>r) return -1;
if (NODE[idx].Left==l&&r==NODE[idx].Right) {
if (NODE[idx].val>c) return NODE[idx].id;
else return -1;
}
int m=(NODE[idx].Left+NODE[idx].Right)>>1;
if (r<=m) return query_Max(l,r,idx<<1,c);
else if (l>m) return query_Max(l,r,idx<<1|1,c);
else {
int L=query_Max(l,m,idx<<1,c);
int R=query_Max(m+1,r,idx<<1|1,c);
if (L==-1) return R;
if (R==-1) return L;
if (val[pos[R]]>=val[pos[L]]) return R;
return L;
}
}
int query(int l, int r, int idx, int c) {
if (l>r) return -1;
if (NODE[idx].Left==l&&r==NODE[idx].Right) {
if (NODE[idx].val<=c) return -1;
if (l==r) {
return l;
} else {
int m=(l+r)>>1;
if (NODE[idx<<1|1].val>c) return query(m+1,r,idx<<1|1,c);
else return query(l,m,idx<<1,c);
}
}
int m=(NODE[idx].Left+NODE[idx].Right)>>1;
if (r<=m) return query(l,r,idx<<1,c);
else if (l>m) return query(l,r,idx<<1|1,c);
else {
int L=query(l,m,idx<<1,c);
int R=query(m+1,r,idx<<1|1,c);
if (R!=-1) return R;
else return L;
}
}
int qu[maxn];
void dfs(int u, int fa) {
sz[u]=1;
f[u]=fa;
dep[u]=dep[fa]+1;
int idx=query(1,dep[u]-1,1,val[u]);
if (idx==-1) dp[u]=1;
else dp[u]=dp[qu[idx]]+1;
Updata(dep[u],1,val[u]);
qu[dep[u]]=u;
int Mx=0;
for (int i=Head[u]; ~i; i=Edge[i].Next) {
int v=Edge[i].to;
if (v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
if (Mx<sz[v]) {
Son[u]=v;
Mx=sz[v];
}
}
Updata(dep[u],1,-val[u]);
}
int dfn[maxn],cnt;
void solve(int u, int top) {
Top[u]=top;
dfn[u]=++cnt;
pos[cnt]=u;
if (Son[u]==0) return;
solve(Son[u],top);
for (int i=Head[u]; ~i; i=Edge[i].Next) {
int v=Edge[i].to;
if (v==f[u]||v==Son[u]) continue;
solve(v,v);
}
}
int main() {
int n,m;
memset(Head,-1,sizeof(Head));
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) scanf("%d",&val[i]);
for (int i=1; i<n; i++) {
int a,b;
scanf("%d%d",&a,&b);
Add(a,b);
}
build(1,n,1);
dfs(1,0);
solve(1,1);
build(1,n,1);
while (m--) {
int u,v,c,res=0;
scanf("%d%d%d",&u,&v,&c);
int Max_id=-1,Max=c,first_Max=-1;
while (Top[u]!=Top[v]) {
if (first_Max==-1) {
int idx=query(dfn[Top[u]],dfn[u],1,c);
if (idx!=-1) {
res=dp[pos[idx]];
first_Max=val[pos[idx]];
}
}
int idx1=query_Max(dfn[Top[u]],dfn[u],1,Max);
if (idx1!=-1) {
Max_id=pos[idx1];
Max=val[pos[idx1]];
}
u=f[Top[u]];
}
if (first_Max==-1) {
int idx=query(dfn[v],dfn[u],1,c);
if (idx!=-1) {
res=dp[pos[idx]];
first_Max=val[pos[idx]];
}
// cout<<"idx="<<idx<<endl;
}
int idx1=query_Max(dfn[v],dfn[u],1,Max);
// cout<<"idx1="<<val[pos[idx1]]<<endl;
if (idx1!=-1) {
Max_id=pos[idx1];
Max=val[pos[idx1]];
}
if (first_Max!=-1) res-=(dp[Max_id]-1);
// cout<<first_Max<<endl;
printf("%d\n",res);
}
return 0;
}
京公网安备 11010502036488号