CIA T13564(luogu)

CIA T13564(luogu)

​​ 题目背景

2017.10.9

leoly的选讲题 题目描述

有一个树状的城市网络（即n个城市由n−1条道路连接的连通图），首都为1号城市，每个城市售卖价值为a[i]的珠宝。

你是一个珠宝商，现在安排有q次行程，每次行程为从u号城市前往v号城市（走最短路径），保证v在u前往首都的最短路径上。

在每次行程开始时，你手上有价值为c的珠宝（每次行程可能不同），并且每经过一个城市时（包括u和v），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。

现在你想要对每一次行程，求出会进行多少次购买事件。 输入输出格式

输入格式：

第一行，两个正整数n,q。

第二行，n个正整数a[i]描述每个城市售卖的珠宝的价值。

接下来n-1行，每行描述一条道路x,y(1≤x,y≤n)，表示有一条连接x和y的道路。

接下来q行，每行描述一次行程u,v,c(1≤u,v≤n)。

输出格式：

对于每次行程输出一行，为所购买次数。 输入输出样例

输入样例#1：

5 4 3 5 1 2 4 1 2 1 3 2 4 3 5 4 2 1 4 2 2 4 2 3 5 1 5

输出样例#1：

2 1 1 0

说明

对于100%的数据，保证2≤n≤10^5,1≤q≤10^5,1≤a[i]≤10^5,1≤c≤10^5。

时间限制：0.5s

内存限制：64M 题意要求我们从下往上找一个最长递升子序列 我们考虑如何去做 我们可以把所有的点连向最近一个比他大的点 那么我们可以在原图中新建一张图 可能这时候画一画样例，我们会觉得找一下深度差就好了 然而新图并没有这么简单，显而易见的结论 我们在新图中仍然需要记录一下他在原图中的深度，每次從从起点往上跳，直到跳到一个在原图中最后一个深度比我大的点 求一下在新图中的深度差就是答案

#include#include#include#define N 220000#define N1 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc(); } return x;}struct node{ int next,y;}data[(N+N1)<<1];int a[N+N1],h[N+N1],num,n,q,Log[N+N1],fa[N+N1][18],max1[N+N1][18],dep[N+N1],arrive[N1];int dep1[N+N1],in[N+N1];void dfs(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x][0]==y) continue;fa[y][0]=x;dep[y]=dep[x]+1;max1[y][0]=a[x]; for (int j=1;j<=Log[dep[y]-1];++j) { fa[y][j]=fa[fa[y][j-1]][j-1];max1[y][j]=max(max1[y][j-1],max1[fa[y][j-1]][j-1]); }dfs(y); }}void dfs1(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x][0]==y) continue;fa[y][0]=x;dep1[y]=dep1[x]+1; for (int j=1;j<=Log[dep1[y]-1];++j) fa[y][j]=fa[fa[y][j-1]][j-1];dfs1(y); }}int main(){ //freopen("13564.in","r",stdin); n=read();q=read();Log[0]=-1; for (int i=1;i<=n+q;++i) Log[i]=Log[i>>1]+1; for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i=0;--j){ if (fa[xx][j]&&max1[xx][j]<=a[i]) xx=fa[xx][j]; }xx=fa[xx][0];if (xx) {in[i]++; data[++num].y=xx;data[num].next=h[i];h[i]=num; data[++num].y=i;data[num].next=h[xx];h[xx]=num; } }memset(fa,0,sizeof(fa)); for (int i=1;i<=n+q;++i)if (!in[i]) dep1[i]=1,dfs1(i); //for (int i=1;i<=n+q;++i) printf("%d %d\n",i,fa[i][0]); for (int i=1;i<=q;++i){ int x=i+n,y=arrive[i],x1=x; for (int j=Log[dep1[x]-1];j>=0;--j){ if (fa[x1][j]&&dep[fa[x1][j]]>=dep[y]) x1=fa[x1][j]; } printf("%d\n",dep1[x]-dep1[x1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。