hdu 6031 Innumerable Ancestors(LCA+剪枝)

题目链接：hdu 6031 Innumerable Ancestors

题意：

给你一棵n个节点的树，现在有m个询问，每次给你两个点集a,b。

让你从a,b点集中选两个点x,y，使得这两个点的LCA的深度最大。

题解：

标解应该是二分+LCA，不过我试了一下暴力，稍微剪了点枝，就直接过去了。

具体看代码

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 const int N=1e5+7,DEG=20;
 5 int ed,g[N],nxt[2*N],v[2*N],fa[N][DEG],dep[N];
 6 
 7 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
 8 
 9 void dfs(int u,int pre){
10     dep[u]=dep[pre]+1,fa[u][0]=pre;
11     F(i,1,DEG-1)fa[u][i]=fa[fa[u][i-1]][i-1];
12     for(int i=g[u];~i;i=nxt[i])if(v[i]!=pre)dfs(v[i],u);
13 }
14 
15 int LCA(int a,int b){
16     if(dep[a]>dep[b])a^=b,b^=a,a^=b;
17     if(dep[a]<dep[b])F(i,0,DEG-1)if((dep[b]-dep[a])&(1<<i))b=fa[b][i];
18     if(a!=b)for(int i=DEG-1;i<0?a=fa[a][0]:0,i>=0;i--)
19     if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
20     return a;
21 }
22 
23 int n,m,a[N],b[N];
24 
25 bool cmp(const int &a,const int &b)
26 {
27     return dep[a]>dep[b];
28 }
29 
30 int main()
31 {
32     while(~scanf("%d%d",&n,&m))
33     {
34         memset(g,-1,sizeof(g));
35         ed=0;
36         F(i,1,n-1)
37         {
38             int x,y;
39             scanf("%d%d",&x,&y);
40             adg(x,y),adg(y,x);
41         }
42         dfs(1,0);
43         F(i,1,m)
44         {
45             int ak,bk;
46             scanf("%d",&ak);
47             F(j,1,ak)scanf("%d",a+j);
48             scanf("%d",&bk);
49             F(j,1,bk)scanf("%d",b+j);
50             sort(a+1,a+1+ak,cmp);
51             sort(b+1,b+1+bk,cmp);
52             int mx=0;
53             F(j,1,ak)
54             {
55                 if(dep[a[j]]<=mx)break;
56                 F(k,1,bk)
57                 {
58                     int lca=LCA(a[j],b[k]);
59                     mx=max(mx,dep[lca]);
60                 }
61             }
62             printf("%d
",mx);
63         }
64     }
65     return 0;
66 }

View Code