如何用服务器发布网站,移动宽带续费多少钱,链接在线缩短,山西响应式网站建设制作「4.4」祖孙询问
题目描述
已知一棵 n 个节点的有根树。有 m 个询问#xff0c;每个询问给出了一对节点的编号 x 和 y#xff0c;询问 x 与 y 的祖孙关系。
输入格式
输入第一行包括一个整数 n 表示节点个数#xff1b; 接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之…
「4.4」祖孙询问
题目描述
已知一棵 n 个节点的有根树。有 m 个询问每个询问给出了一对节点的编号 x 和 y询问 x 与 y 的祖孙关系。
输入格式
输入第一行包括一个整数 n 表示节点个数 接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 -1那么 a 就是树的根 第 n2 行是一个整数 m 表示询问个数 接下来 m 行每行两个正整数 x 和 y表示一个询问。
输出格式
对于每一个询问若 x 是 y 的祖先则输出 1若 y 是 x 的祖先则输出 2否则输出 0。
样例输入1
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
1 0 0 0 2
注释说明
对于 30% 的数据1≤n,m≤10^3 对于 100% 的数据1≤n,m≤4×10^4每个节点的编号都不超过 4×10^4。
#includebits/stdc.h
using namespace std;
const int N4e55;
int n,pre[N],f[N][17],dep[N],k,lg[N];
struct node{int to,next;
}e[N*2];
void add(int u,int v){e[k](node){v,pre[u]};pre[u]k;
}
void dfs(int x,int fa){f[x][0]fa;dep[x]dep[fa]1;for(int ipre[x];i!0;ie[i].next){int toe[i].to;if(tofa)continue;dfs(to,x);}
}
int lca(int x,int y){if(dep[x]dep[y])swap(x,y);while(dep[x]dep[y])xf[x][lg[dep[x]-dep[y]]];if(xy)return x;for(int i16;i0;i--){if(f[x][i]!f[y][i]){//printf((%d,%d),f[x][i],f[y][i]);xf[x][i];yf[y][i];}}return f[x][0];
}
int main(){scanf(%d,n);int rt,x,y;for(int i1;in;i){scanf(%d%d,x,y);if(y-1){rtx;continue;}add(x,y);add(y,x);}dfs(rt,0);for(int i2;iN;i)lg[i]lg[i/2]1;for(int j1;j16;j){for(int i1;iN;i){f[i][j]f[f[i][j-1]][j-1];}}int m;scanf(%d,m);while(m--){scanf(%d%d,x,y);int lclca(x,y);//printf(%d\n,lc);if(lcx)puts(1);else if(lcy)puts(2);else puts(0);}
}
/*
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 234
234 17
233 13
233 15
233 19
*/
