首页 > 代码库 > UVAlive3486_Cells

UVAlive3486_Cells

2024-07-14 11:49:06   212人阅读

给一棵树，每次每次询问一个点是否是另一个点的祖先？

首先，题目的读入就有点坑爹，注意，每个节点的值是说明它下面有多少个儿子节点，直接对于每个下标保存一个值即可。

对于查询是否是祖先，我们可以对于每一个节点打上两个dfs标记，如果一个点是另一个点的祖先，那么它的两个标记一定在祖先的范围之内。

还要注意，由于点数极其多，直接dfs会爆栈，那么我们需要手动模拟栈的执行过程。简单，数组模拟就好了。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#include <vector>#define maxn 20022000using namespace std;int l[maxn],r[maxn],sum[333333];bool a[maxn];int T,n,k,m,cur,TAG=222,dfs_clock,cas=0;int stack[maxn],top;void dfs(){    for (int i=0; i<maxn; i++) a[i]=false;    dfs_clock=stack[top=1]=0;    while (top>0){        k=stack[top];        if (!a[k]){            a[k]=true,l[k]=++dfs_clock;            if (k<n)                for (int i=k==0?1:sum[k-1]+1; i<=sum[k]; i++) stack[++top]=i;        }        else r[k]=++dfs_clock,top--;    }}int main(){    int x,y;    scanf("%d",&T);    while (T--){        scanf("%d",&n);        for (int i=0; i<n; i++){            scanf("%d",&k);            sum[i]=i==0?k:sum[i-1]+k;        }        dfs();        if (cas++) printf("\n");        printf("Case %d:\n",cas);        scanf("%d",&m);        while (m--){            scanf("%d%d",&x,&y);            if (l[x]<l[y] && r[x]>r[y]) puts("Yes");                else puts("No");        }    }    return 0;}

 


联系
我们