题目链接

我焯，这个是真的难…

参考题解

分析：

1.

首先，题目给的是一个图，但是通过样例我们发现并不需要那么多的边；
贪心的想，我们只需要最靠前的边使得所有节点连通就行了；
因此我们把边的编号当作边权，求一下MST（最小生成树）；
那么我们的答案一定是在这个MST上找的；

2.

对于具体询问，我们转换一下问题：
原问题就转换成：给[l,r]，求l~r之间所有点形成的连通块的最大边权；
注意这里是在MST上的，所以给一个[l,r]，连通块都是确定的。（到这里就不会了…）

3.（注意这里我们都是在MST上搞的！）

这个有个知识盲点我不会…连续区间求lca一定是连通的；
先说结论吧：
如果我们能预处理出相邻两个点(i-1,i)路径上的边权的最大值mx[i]；
那么每次查询[l,r]，答案就是max(mx[i]);
因此我们可以用线段树维护mx[i]最值，每次询问[l,r]直接查一下就行；

4. 如何算出相邻两个点(i-1,i)路径上的边权的最大值mx[i]？？？

注意到任意两个点在树上的路径是唯一的，可以用lca来求！
因此我们可以在求lca的时候顺便求出两点路径上的边权mx。
这个就考到了对lca的理解了…不能光贴板子…
我们可以维护一个f_max[i][j]，表示i这个点往上跳j步过程中的一个最大边权；
然后在bfs时 和 求lca时同时维护这个数组就行，这就比较简单了。

为什么维护相邻的点的lca这样做是对的？
首先就是任意两个点在树上的路径是确定的，唯一的；
其次连续区间内任意两点的lca一定包含在若干个[i,i+1]的lca内部，因为是一个连通图。

究极缝合怪，细节还是非常多的。

代码

#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)

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 = 2e5 + 7;
const int N = 1e6 + 7;
const int M = 1e6 + 7;
const int mod = 998244353;
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,m,q;
int h[maxn],ne[maxn*2],e[maxn*2],w[maxn*2],idx;
int ff[maxn];	//并查集
int v[maxn];	//v[i]表示i到i-1路径上边权最大值

struct node	//线段树
{
	int l,r;
	int mx;
}tr[maxn*4];

//lca
int depth[maxn],f[maxn][22];    //2^15 > 4e4，所以15就可以跳完所有边
int f_max[maxn][22];	//每个点往上跳2^j过程中的最大边权

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

void bfs(int root)  //预处理depth[] 和 f[][]数组, 从根开始向下更新 
{
    for(int i=0;i<=n;i++) depth[i] = inf;
    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;   //子节点跳一步到父节点
                f_max[j][0] = w[i];
    
                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)
                	f_max[j][k] = max(f_max[j][k-1],f_max[f[j][k-1]][k-1]);
				}          
            }
        }   
    }
}

int lca(int a,int b)	//边求lca，边求最大值
{
	int ans = 0;
    //第一步，两个点先跳到同一层
    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，则可以跳
        {
        	ans = max(ans,f_max[a][k]);	//注意先更新ans！
        	a = f[a][k];
		}

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

    //否则，a b同时往上跳
    for(int k=19; k>=0; k--)
        if(f[a][k] != f[b][k])  //跳完之后不相等一直跳 
        {
        	ans = max(ans,max(f_max[a][k],f_max[b][k]));
            a = f[a][k];
            b = f[b][k];    //跳到最近公共祖先的下一层为止 
        }
	
	//最后再往上跳一步，两个都要更新！
	ans = max(ans,max(f_max[a][0],f_max[b][0]));
	
    return ans; //在往上跳一步就是最近公共祖先了
}

void init()
{
	for(int i=0;i<=n;i++)
	{
		h[i] = -1;
		ff[i] = i;
		v[i] = 0;
		for(int j=0;j<22;j++) f[i][j] = f_max[i][j] = 0;
	}
	idx = 0;
}

void pushup(int u)
{
	tr[u].mx = max(tr[u<<1].mx, tr[u<<1|1].mx);
}

void build(int u,int l,int r)
{
	tr[u] = {l,r};
	
	if(l == r) 
	{
		tr[u].mx = v[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

int query(int u,int l,int r)
{
	if(l <= tr[u].l && r >= tr[u].r) return tr[u].mx;
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	int ans = 0;
	if(l <= mid) ans = max(ans,query(u<<1, l, r));
	if(r > mid) ans = max(ans,query(u<<1|1, l, r));
	
	return ans;
}

int find(int x)
{
	return ff[x] == x ? x : ff[x]=find(ff[x]);
}

void solve()
{
	iire(n,m);
	ire(q);
	
	init();	//初始化
	
	//重构树，求MST
	for(int i=1;i<=m;i++)
	{
		int a,b;
		iire(a,b);
		
		int fa = find(a);
		int fb = find(b);
		
		if(fa != fb)
		{
			ff[fa] = fb;
			add(a,b,i);
			add(b,a,i);
		}
	}
	
	bfs(1);  //预处理depth[] 和 f[][]数组
	
	for(int i=2;i<=n;i++) v[i] = lca(i-1,i);	//边求lca，边求最大值
	
	build(1,1,n);	//建线段树，维护区间最大值
	
	while(q--)
	{
		int l,r;
		iire(l,r);
		
		if(l == r) cout<<"0 ";
		else cout<<query(1,l+1,r)<<' ';
	}
	cout<<endl;
}

int main()
{
	int t;
	ire(t);
	while(t--)
	{
		solve();
	}
	
	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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249