首页 > 代码库 > HDU 6031 Innumerable Ancestors
HDU 6031 Innumerable Ancestors
树状数组，倍增，枚举，$dfs$序。
对于每一次的询问，可以枚举$B$集合中的所有点，对于每一个点，在树上二分$LCA$，找到最低的更新答案。
判断是否是$LCA$可以搞个$dfs$序，将$A$集合中所有点标$1$，然后查询子树对应的区间上的区间和。
#include <bits/stdc++.h>using namespace std;const int maxn = 100010;int L[maxn],R[maxn];int c[2*maxn];int h[maxn];int to[2*maxn];int nx[2*maxn];int sz;int tt;int dp[100010][25];int dep[100010];int ans;int n,m;int k1,k2;int A[100010],B[100010];void add(int a,int b){ to[sz] = b; nx[sz] = h[a]; h[a] = sz++;}void dfs(int x,int y){ L[x] = tt; tt++; dp[x][0] = y; if(y==-1) dep[x]=1; else dep[x] = dep[y]+1; for(int i=h[x];i!=-1;i = nx[i]) { if(L[to[i]]) continue; dfs(to[i],x); } R[x] = tt; tt++;}int lowbit(int x){ return x&(-x);}void update(int pos,int val){ for(int i=pos;i<=2*n;i=i+lowbit(i)) { c[i] += val; }}int get(int pos){ int res=0; for(int i=pos;i>0;i=i-lowbit(i)) { res=res+c[i]; } return res;}void work(int x){ while(1) { int Q = dp[x][0]; if(get(R[Q])-get(L[Q]-1)) { ans = max(ans,dep[Q]); break; } for(int i=17;i>=0;i--) { int to = dp[x][i]; if(to==-1) continue; if(get(R[to])-get(L[to]-1)) continue; x=to; break; } } x = dp[x][0]; ans = max(ans,dep[x]);}int main(){ while(~scanf("%d%d",&n,&m)) { sz=0; for(int i=0;i<=n;i++) { c[i]=0; h[i]=-1; L[i]=0; R[i]=0; } for(int i=1;i<=n-1;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } tt=1; dfs(1,-1); for(int j=1;j<=17;j++) { for(int i=1;i<=n;i++) { if(dp[i][j-1]==-1) dp[i][j]=-1; else dp[i][j] = dp[dp[i][j-1]][j-1]; } } for(int i=1;i<=m;i++) { scanf("%d",&k1); for(int j=1;j<=k1;j++) scanf("%d",&A[j]), update(L[A[j]],1); scanf("%d",&k2); ans=0; for(int j=1;j<=k2;j++) { scanf("%d",&B[j]); if(get(R[B[j]])-get(L[B[j]]-1)) { ans = max(ans,dep[B[j]]); continue; } work(B[j]); } printf("%d\n",ans); for(int j=1;j<=k1;j++) update(L[A[j]],-1); } } return 0;}
HDU 6031 Innumerable Ancestors
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。