tree(2018.10.26)

题意：给你一颗树，树上每个节点都有一个权值，多次询问树上的一条链的严格上升子序列长度

这道题是个神奇的倍增，先记录\(fa[x][0]\)为\(x-root\)路径上第一个权值比他大的点，然后顺便处理出需要跳几步能跳到最靠近根的那个比他大的点（即上升子序列的长度）

对于询问，倍增询问即可。

细节：

1、对于查询路径上第一个权值比他大的点，我们显然只能用\(O(logn)\)的时间，所以我们采用二分查找，可是这条路径上的点并不能保证单调性，所以我们考虑维护一个单调的序列，假设我们对于一个点\(y\)找到路径上第一个权值比他大的点，假设这个点为\(x\)，那么对于之后的点，\(x\)后面的那个点就没有价值了，就用\(y\)取代那个点，就好了。

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int f[100005][20],top,st[1000005],dep[100005],dis[100005],n,q,cnt,pre[200005],nxt[200005],h[100005],w[100005];

void add(int x,int y)

{

    pre[++cnt]=y;nxt[cnt]=h[x];h[x]=cnt;

    pre[++cnt]=x;nxt[cnt]=h[y];h[y]=cnt;

}

bool cmp(int a,int b){return w[a]>w[b];}

void dfs(int x,int fa)

{

    int ttt=top;top=lower_bound(st+1,st+ttt+1,x,cmp)-st-1;

    f[x][0]=st[top++];dis[x]=dis[f[x][0]]+1;int nowid=top,nowval=st[top];st[top]=x;

    for(int i=h[x];i;i=nxt[i])if(pre[i]!=fa)dep[pre[i]]=dep[x]+1,dfs(pre[i],x);

    st[nowid]=nowval;top=ttt;

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),add(x,y);

    dep[1]=1;dfs(1,0);

    for(int i=1;i<20;i++)

        for(int j=1;j<=n;j++)

            f[j][i]=f[f[j][i-1]][i-1];

    for(int i=1,x,y,c;i<=q;i++)

    {

        scanf("%d%d%d",&x,&y,&c);

        int p=x;if(c>=w[x]){for(int i=19;i>=0;i--)if(f[p][i]&&w[f[p][i]]<=c)p=f[p][i];p=f[p][0];}

        if(dep[p]<dep[y])printf("0\n");

        else

        {

            int s=p;for(int i=19;i>=0;i--)if(dep[f[s][i]]>=dep[y])s=f[s][i];

            printf("%d\n",dis[p]-dis[s]+1);

        }

    }

}

巴特西

tree(2018.10.26)

最新文章

热门文章