HDU6024 Innumerable Ancestors

2017女生赛, HDU, LCA, 二分

　　2017中国大学生程序设计竞赛 - 女生专场

　　题意：给定一棵树，有m次询问，每次询问给出点集X和点集Y，在X中找到一点u，在Y中找到一点v，使得dep(lca(u, v))最大。 - 原题链接

　　队友提供的思路，并未严格证明：对于每次询问，将点集Y中的点按dfs序排序，枚举点集X中的点u，二分点集Y找到和点u的dfs序最近的点v，求dep(lca(u, v))。

　　因为case数不超过5，且保证每个case的∑k≤100000，时间复杂度并无压力。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=400000+10;
int n, m, tot, rmq[maxn], P[maxn], F[maxn];
int cur, fir[maxn], nxt[maxn], ver[maxn];
int xk, yk, x[maxn], y[maxn];
bool vis[maxn];
struct ST
{
    int mm[maxn], dp[maxn][20];
    void init(int n)
    {
        mm[0]=-1;
        for(int i=1; i<=n; i++)
        {
            mm[i]=((i&(i-1))==0) ? mm[i-1]+1 : mm[i-1];
            dp[i][0]=i;
        }
        
        for(int j=1; j<=mm[n]; j++)
            for(int i=1; i+(1<<j)-1<=n; i++)
                dp[i][j]=rmq[dp[i][j-1]] < rmq[dp[i+(1<<(j-1))][j-1]] ? dp[i][j-1] : dp[i+(1<<(j-1))][j-1];
    }
    int query(int a, int b)
    {
        if(a>b) swap(a, b);
        int k=mm[b-a+1];
        return rmq[dp[a][k]] <= rmq[dp[b-(1<<k)+1][k]] ? dp[a][k] : dp[b-(1<<k)+1][k];
    }
}st;
void Add(int u, int v)
{
    ver[++cur]=v, nxt[cur]=fir[u], fir[u]=cur;
    ver[++cur]=u, nxt[cur]=fir[v], fir[v]=cur;
    return ;
}
int query(int u, int v)
{
    return rmq[st.query(P[u], P[v])];
}
bool cmp(int a, int b)
{
	return P[a]<P[b];
}
int Work()
{
    int ans=0, cnt, u;
	
	sort(y, y+yk, cmp);
    
	for(int i=0; i<xk; i++)
    {
		u=x[i];
		cnt=lower_bound(y, y+yk, u, cmp)-y;
        if(cnt<yk) ans=max(ans, query(x[i], y[cnt]));
        if(cnt>0)   ans=max(ans, query(x[i], y[cnt-1]));
    }
    return ans;
}
void Dfs(int u, int d)
{
    vis[u]=true;
    F[++tot]=u;
    rmq[tot]=d;
    P[u]=tot;
    
    for(int i=fir[u], v; i ; i=nxt[i])
        if(!vis[v=ver[i]])
        {
            Dfs(v, d+1);
            F[++tot]=u;
            rmq[tot]=d;
        }
    return ;
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        cur=0;
        memset(fir, 0, sizeof fir);
        for(int i=1, u, v; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            Add(u, v);
        }
        
        memset(vis, 0, sizeof vis);
        memset(P, 0, sizeof P);
        memset(F, 0, sizeof F);
        memset(rmq, 0, sizeof rmq);
        tot=0;
        Dfs(1, 0);
        st.init(2*n-1);
        
        
        for(int i=1; i<=m; i++)
        {
            scanf("%d", &xk);
			for(int j=0; j<xk; j++)	scanf("%d", &x[j]);
			scanf("%d", &yk);
			for(int j=0; j<yk; j++)	scanf("%d", &y[j]);
            printf("%d\n", Work()+1);
        }
    }
    return 0;
}