解题思路:
常规的求祖先方法往往一次向上移动1,采用倍增的方法一次向上移动2^k,nlogn处理出倍增数组,logn查询。
注意事项:
提一个题解区没说的,不要用cin读,会超时。
参考代码:
#include<bits/stdc++.h> using namespace std; #define maxx 130000 #define int long long int n,q,a,b; int fa[maxx]; int faaa[maxx][22]; vector<int> G[maxx]; int dep[maxx]; void starting() { for(int i=1;i<=n;++i) faaa[i][0]=fa[i]; for(int j=1;j<=20;++j) //循环位置 for(int i=1;i<=n;++i) faaa[i][j]=faaa[faaa[i][j-1]][j-1]; } void dfs(int i) { for(int j=0;j<G[i].size();++j) {dep[G[i][j]]=dep[i]+1; dfs(G[i][j]);} } int cal(int x,int y) { if(dep[x]>dep[y]) return 0; int cha=dep[y]-dep[x]; for(int i=0;i<20;++i) { if(cha%2==1) y=faaa[y][i]; cha/=2; } if(y==x) return 1; else return 0; } signed main() { scanf("%d %d",&n,&q); for(int i=1;i<n;++i) {scanf("%d %d",&a,&b); fa[b]=a; G[a].push_back(b); } for(int i=1;i<=n;++i) if(fa[i]==0) dfs(i); starting(); for(int i=1;i<=q;++i) { scanf("%d %d",&a,&b); if(cal(a,b)) cout<<"YES\n"; else cout<<"NO\n"; } }
0.0分
1 人评分
字符串比较 (C语言代码)答案错误????浏览:597 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:624 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:669 |
回文数字 (C语言代码)浏览:2510 |
DNA (C语言代码)浏览:747 |
数组与指针的问题浏览:716 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:563 |
A+B for Input-Output Practice (III) (C语言代码)浏览:421 |
C语言训练-排序问题<1> (C语言代码)浏览:355 |