这个题好啊!

题目连接

思维 + lca

参考的题解

分析

转换一下题目，变成[1~n]里到点集S的最远距离最小的结果;
而这个点应该出现在点集S中离得最远的两个点连线的中点上。
（如果不是在中点上，则f[u]必然会增大，使得我们的答案变大）

那么问题就转换成：
每次给一个集合S，求S中距离最远的两个点的距离ans；
当S包含所有点的时候也就是求树的直径，这个也是类似的求直径；
众所周知，求树的直径可以先找一个深度最深的点，再以这个点做根找最远的另一个点；
时间复杂度是O(n)的，每次询问来这么一下肯定不行；

对于一个集合S，我们还是首先找深度最深的点u；
然后再遍历S中的点v找离u距离最远的点，树上求两点距离，可以用lca快速算出；

所以lca预处理一下就行，每一次询问的时间复杂度是O(|S|*log(n));
最终答案就是 ceil(ans/2).

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 1e6 + 7;
const int N = 1e6 + 7;
const int M = 1e6 + 7;
const int mod = 3*5*7*11*13*17*19*23;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int n;
int h[maxn],ne[maxn*2],e[maxn*2],idx;
int depth[maxn],f[maxn][20];    //2^15 > 4e4，所以15就可以跳完所有边

void add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}

void bfs(int root)  //预处理depth[] 和 f[][]数组, 从根开始向下更新 
{
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0;       //设置哨兵，处理跳出根节点了 
    depth[root] = 1;

    queue<int> q;
    q.push(root);

    while(q.size())
    {
        int no = q.front(); //父节点 
        q.pop();

        for(int i=h[no]; i!=-1; i=ne[i])    //子节点 
        {
            int j = e[i];

            //更新两个数组
            if(depth[j] > depth[no] + 1)    //还没更新过
            {
                depth[j] = depth[no] + 1;

                q.push(j);

                f[j][0] = no;   //子节点跳一步到父节点
                for(int k=1; k<=19; k++)    //枚举往上跳2^k步 
                    f[j][k] = f[f[j][k-1]][k-1];    //2^k = 2^(k-1) + 2^(k-1)               
            }
        }   
    }
}

int lca(int a,int b)
{
    //第一步，两个点先跳到同一层
    if(depth[a] < depth[b]) swap(a,b);  //让a跳到b那一层
    for(int k=19; k>=0; k--)    //从大到小枚举跳的步数
        if(depth[f[a][k]] >= depth[b])  //如果a跳完之后不超过b，则可以跳 
            a = f[a][k];

    if(a == b) return b;    //跳到同一层后相等说明b就是公共祖先了

    //否则，a b同时往上跳 
    for(int k=19; k>=0; k--)
        if(f[a][k] != f[b][k])  //跳完之后不相等一直跳 
        {
            a = f[a][k];
            b = f[b][k];    //跳到最近公共祖先的下一层为止 
        }

    return f[a][0]; //在往上跳一步就是最近公共祖先了 
}

int cal(int a,int b)
{
	return depth[a] + depth[b] - 2*depth[lca(a,b)];
}

int main()
{
	memset(h,-1,sizeof h);
	
	ire(n);
	for(int i=2;i<=n;i++)
	{
		int a,b;
		iire(a,b);
		add(a,b);
		add(b,a);
	}
	
	bfs(1);

	int q;
	ire(q);
	while(q--)
	{
		int cnt;
		ire(cnt);
		
		vector<int> v;
		
		int u = -1;	//深度最大的点
		int mx = -1;	
		
		for(int i=1;i<=cnt;i++)
		{
			int x; ire(x);
			v.push_back(x);
			
			if(depth[x] > mx) mx = depth[x], u = x;
		}

		int ans = -1;
		for(auto x : v) ans = max(ans,cal(u,x));
		
		cout<<(ans+1)/2<<'\n';
	}
	
	return 0;
}


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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171