bzoj 5479 tree

Posted on | Views:

欧拉序 + 贪心 + 二分.

  • $LCA$ 问题首先可以处理出欧拉序,将树上问题转化成序列问题.
  • 于是就变成了给出一些 $A$ 类点,一些 $B$ 类点,选两个不同类的点作为区间,求区间内 $dep$ 的最小值的最大值.
  • 看上去可以直接二分,然而没什么用,因为区间数目是 $|A|\cdot |B|$ 的.
  • 考虑贪心.对于一个 $B$ 类点,如果我们钦定它作为左端点,那么那个作为右端点的 $A$ 类点应该越靠左越好.如果钦定它为右端点,那么那个 $A$ 类点应该越靠左越好.
  • 于是对每个 $B$ 类点二分出左/右最近的 $A$ 类点,将这两个区间的 $dep$ 最小值加入贡献.
  • 预处理 $ST$ 表,时间复杂度 $O(\sum |B| \cdot log|A|)$ .
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,m;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int dep[MAXN],dfn[MAXN],idx;
int a[MAXN<<1];
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	dfn[u]=++idx;
	a[idx]=dep[u];
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa)
			continue;
		dfs(v,u);
		a[++idx]=dep[u];
	}
}
const int LogN=20;
int st[MAXN<<1][LogN];
int Log[MAXN<<1];
void init_ST()
{
	for(int i=1;i<=2*n-1;++i)
		st[i][0]=a[i];
	for(int j=1;(1<<j)<=2*n-1;++j)
		for(int i=1;i+(1<<j)-1<=2*n-1;++i)
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
	int k=Log[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
void reset()
{
	ecnt=0;
	idx=0;
	for(int i=1;i<=n;++i)
		head[i]=0;
}
int dfnset[MAXN<<1],A;
int pre(int x)
{
	return dfnset[upper_bound(dfnset,dfnset+A,x)-dfnset-1];
}
int suf(int x)
{
	return dfnset[lower_bound(dfnset,dfnset+A,x)-dfnset];
}
int main()
{
	Log[1]=0;
	for(int i=2;i<=200000;++i)
		Log[i]=Log[i>>1]+1;
	int T=read();
	while(T--)
	{
		n=read(),m=read();
		reset();
		for(int i=1;i<n;++i)
		{
			int u=read(),v=read();
			addedge(u,v);
			addedge(v,u);
		}
		dfs(1,0);
		init_ST();
		while(m--)
		{
			int ans=0;
			A=read();
			for(int i=1;i<=A;++i)
				dfnset[i]=dfn[read()];
			sort(dfnset+1,dfnset+1+A);
			dfnset[0]=0,dfnset[A+1]=2*n;
			A+=2;
			int B=read();
			for(int i=1;i<=B;++i)
			{
				int x=dfn[read()];
				int lx=pre(x),rx=suf(x);
				if(lx)
					ans=max(ans,query(lx,x));
				if(rx!=2*n)
					ans=max(ans,query(x,rx));
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}