传送门:https://codeforces.com/problemset/problem/1328/E
题意:n个结点的树 m次询问 让你找一条从根结点1开始的路径 使一些点在路径上或离路径上的点距离为1 问能不能找到
因为是要求这些点在路径上或者离路径上的点的距离为1,所以可以把每个点处理为他的父节点,然后再考虑(妙)
这样问题就变成这些点是不是都在一条路上,这条路还得从1开始
按照深度排序,看深的能不能走到浅的那里(看最近公共祖先是不是深度小的那个点),就可以啦
算是一道lca吧
关于倍增lca可以看我https://www.cnblogs.com/YangKun-/p/12524015.html的另一篇博客
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=1e6+10; 5 const int inf=0x3f3f3f3f; 6 vector<int>ve[200009]; 7 int vis[200009],father[200009][25]; 8 int now[200009]; 9 int deep[200009]; 10 void dfs(int u) 11 { 12 for(int i=0; i<ve[u].size(); i++) 13 { 14 int v=ve[u][i]; 15 if(vis[v]==0) 16 { 17 father[v][0]=u;//记得初始化 18 vis[v]=1; 19 deep[v]=deep[u]+1; 20 dfs(v); 21 } 22 } 23 } 24 void st(int n) 25 { 26 for(int j=1; (1<<j)<=n; j++) 27 for(int i=1; i<=n; i++) 28 father[i][j]=father[father[i][j-1]][j-1]; 29 } 30 int lca(int u,int v) 31 { 32 int h=deep[u]-deep[v]; 33 for(int i=0; i<20; i++) 34 { 35 if(h&(1<<i)) 36 { 37 u=father[u][i]; 38 } 39 } 40 if(u==v) return u; 41 else return -1; 42 } 43 int cmp(int a,int b) 44 { 45 return deep[a]>deep[b]; 46 } 47 int main() 48 { 49 int n,m,l,r; 50 scanf("%d%d",&n,&m); 51 for(int i=1; i<n; i++) 52 { 53 scanf("%d%d",&l,&r); 54 ve[l].push_back(r); 55 ve[r].push_back(l); 56 } 57 vis[1]=1; 58 deep[1]=1; 59 father[1][0]=0; 60 dfs(1); 61 st(n); 62 // for(int i=0;i<=n;i++) printf("deep[%d]=%d\n",i,deep[i]); 63 while(m--) 64 { 65 int k; 66 scanf("%d",&k); 67 for(int i=1; i<=k; i++) 68 { 69 scanf("%d",&now[i]); 70 now[i]=father[now[i]][0]; 71 // printf("%d ",now[i]); 72 } 73 sort(now+1,now+1+k,cmp); 74 int flag=0; 75 for(int i=1; i<k; i++) 76 { 77 if(lca(now[i],now[i+1])==-1) 78 { 79 flag=1; 80 break; 81 } 82 } 83 if(flag) printf("NO\n"); 84 else printf("YES\n"); 85 } 86 return 0; 87 }
原文:https://www.cnblogs.com/YangKun-/p/12589854.html