「NOIP模拟赛」祖孙询问
「问题描述」
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
「输入格式」
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行，每行两个正整数x和y。
「输出格式」
对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。
「样例输入」
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
「样例输出」
1
0
0
0
2
「数据规模」
对于30%的数据，n,m≤1000。
对于100%的.据,n,m≤40000，每个节点的编号都不超过40000。
题解
直接上lca或者dfs序
听说会爆栈我写了bfs的lca
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[16]; int n,m,root,cnt; int q[40005],deep[40005],fa[40005][16]; bool vis[40005]; struct data{int to,next;}e[80005];int last[40005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void bfs() { int head=0,tail=1; q[0]=root;vis[root]=1; while(head!=tail) { int now=q[head];head++; for(int i=1;i<=15;i++) if(bin[i]<=deep[now]) fa[now][i]=fa[fa[now][i-1]][i-1]; else break; for(int i=last[now];i;i=e[i].next) if(!vis[e[i].to]) { deep[e[i].to]=deep[now]+1; fa[e[i].to][0]=now; vis[e[i].to]=1; q[tail++]=e[i].to; } } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=15;i++) if(t&bin[i])x=fa[x][i]; for(int i=15;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if(x==y)return y; return fa[x][0]; } int main() { //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<=n;i++) { int u=read(),v=read(); if(v==-1)root=u; else insert(u,v); } bfs(); m=read(); for(int i=1;i<=m;i++) { int a=read(),b=read(),t=lca(a,b); if(a==t&&b!=t)puts("1"); else if(a!=t&&b==t)puts("2"); else puts("0"); } return 0; } |
Subscribe
计数器 9855208
OI 课件=>
OI 课件=>