CF1648F 题解

First Post:

Last Update:

一道 Educational 的题，做完后学到了很多！

显然，如果我们割去一条边的话，我们显然会割一座桥。

所以就有一个思路是把边双缩一下，然后考虑割掉两座桥的贡献。

但是因为这里是割两条边，所以其实可以割两条边双内的边，这不好处理。

所以这个思路是错误的，边双内的问题和原图的问题本质相同，不好处理。

那我们换个思路，既然这是个连通性问题，考虑一个 DFS 树。

对于每条树边 ，设 对关键点中，在树上的路径经过 的点对数为 ，设在 条非树边中，覆盖树边 的非树边集合为 （"覆盖"是指端点在树上的路径经过 ）。在实现时，可以对每个非树边赋一个 的随机权值，树边权值为覆盖其的非树边权值的异或和。这样就可以比较 和 的关系了。

考虑答案的几种情况：

  1. 割两条割边。因为割边肯定是树边，答案为 ，满足
  2. 割一条树边，同时割掉覆盖它的所有非树边，这种情况需要 ，贡献为 。
  3. 割两条树边，这是本题最难的情况。这两条树边需要满足 。也就是说，在割了这两条边之后，原树会分成三个部分。我们要求没有非树边连接中间的部分与两边的部分。此时的贡献为 “恰好 跨过 中一条边的关键点路径数”。

前两种情况较为平凡，考虑第三种。

设 表示同时经过 和 的路径数，那么贡献就是 。

发掘 和 的性质。

  1. 因为 DFS 树上的非树边都是祖先连向后代的边，所以要使得 ， 和 之间也必然是祖先-后代的关系。

  2. 另一方面，一条链上的 不会出现类似 的情况，即每种 的出现区间包含而不交叉，这个也是可以手画来理解的。

性质 对另一个做法会有所帮助，但我们这里不讲。

考虑基于性质 ，我们如何快速算出 。

因为 是祖先-后代关系，我们可以将关键点路径 拆成两条不相干的路径 ，并在对应的 点和 点记录这两条路径。

注意到在固定 的时候， 和 具有相同的含义，都可以确定一条边，所以我们对每个点 建立一棵以 为下标的线段树。处理到一个点时，我们取出这个点上记录的路径 ，并在 点的线段树上，将 对应的值 。做完后，再把子树内的线段树合并即可。

查询的时候，我们只需查询 对应的线段树（实际上是 的端点中深度较深的那个对应的线段树）中， 的区间和即可 （ 指 端点中深度较浅的那个）。

但我们还是要统计很多对 的贡献。

注意到在固定 的时候， 是具有决策单调性的。

即对于 ，它们对应的 一定有 。

这个可以通过四边形不等式，交叉优于包含来证明。

所以在处理一种 时，把属于那种颜色的边全部取出来，跑一个决策单调性分治即可。

时间复杂度 ，空间卡得很紧。

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
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5,M = N << 1;
typedef unsigned long long ull;
typedef tuple<int,int,int> Ans_t;
typedef pair<int,int> pii;
#define FI first
#define SE second
#define mkp make_pair
#define mkt make_tuple
template<typename T> inline void ckmax(T &x,const T &y) { if(x < y) x = y;}

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

int n,m,Q,mxdep;
int U[N],V[N];
int fir[N],nxt[M],to[M],Id[M],ect = 1;
inline void addedge(int u1,int v1,int id1)
{
	nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;Id[ect] = id1;
}
// int dfs_seq[N];
vector<int> G[N];
int dep[N],fa[N];
bool intree[N];
int fa_id[N];
bool vis[N];
void dfs0(int x,int from)
{
	vis[x] = true;
	for(int i = fir[x],y;y = to[i],i;i = nxt[i])
	{
		if((from ^ 1) == i) continue;
		if(!vis[y]) {
			dep[y] = dep[x] + 1;fa[y] = x;
			intree[Id[i]] = true;
			fa_id[y] = Id[i];
			dfs0(y,i);
			G[x].push_back(y);
		}
	}
}
mt19937_64 Rnd(1919810);
ull hsh[N];
int cov[N];
// void dfssum()
// {
// 	for(int i = n;i >= 1;i--)
// 	{
// 		int u = dfs_seq[i];
// 		if(u == 1) continue;
// 		cov[fa[u]] += cov[u];
// 		hsh[fa[u]] ^= hsh[u];
// 	}
// }
void dfssum(int x)
{
	for(auto y : G[x])
		dfssum(y),hsh[x] ^= hsh[y],cov[x] += cov[y];
}
const int Sz = N * 60;
int lc[Sz],rc[Sz],sum[Sz],rt[N],tot = 0;
inline int NewNode() { int k = ++tot;sum[k] = lc[k] = rc[k] = 0;return k;}
inline void pushup(int x) { sum[x] = sum[lc[x]] + sum[rc[x]];}
void modify(int &k,int l,int r,int pos,int v)
{
	if(!k) k = ++tot;
	sum[k] += v;
	if(l == r) {return;}
	int mid = l + r >> 1;
	if(pos <= mid) modify(lc[k],l,mid,pos,v);
	else modify(rc[k],mid + 1,r,pos,v);
}
int Qsum(int k,int l,int r,int x,int y)
{
	if(!k) return 0;
	if(x <= l && r <= y) return sum[k];
	int mid = l + r >> 1;
	if(y <= mid) return Qsum(lc[k],l,mid,x,y);
	else if(x > mid) return Qsum(rc[k],mid + 1,r,x,y);
	else return Qsum(lc[k],l,mid,x,y) + Qsum(rc[k],mid + 1,r,x,y);
}
int Merge(int x,int y,int l,int r)
{
	if(!x || !y) return x + y;
	int nd = NewNode();
	if(l == r) {sum[nd] = sum[x] + sum[y];return nd;}
	int mid = l + r >> 1;
	lc[nd] = Merge(lc[x],lc[y],l,mid);
	rc[nd] = Merge(rc[x],rc[y],mid + 1,r);
	sum[nd] = sum[x] + sum[y];
	return nd;
}

int sze[N],son[N],top[N];

void dfs1(int x)
{
	sze[x] = 1;
	for(auto y : G[x])
	{
		dfs1(y);
		sze[x] += sze[y];
		if(sze[y] > sze[son[x]]) son[x] = y;
	}
}
void dfs2(int x,int topt)
{
	top[x] = topt;
	if(son[x]) dfs2(son[x],topt);
	for(auto y : G[x])
		if(y != son[x]) dfs2(y,y);
}
int lca(int x,int y)
{
	while(top[x] != top[y])
		dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
	return dep[x] < dep[y] ? x : y;
}
vector<int> Chg[N];

inline int calc(int x,int y) { 
    // printf("calc:%d,%d,%d\n",x,y,cov[x] + cov[y] - 2 * Qsum(rt[y],0,n,0,dep[x] - 1));
    return cov[x] + cov[y] - 2 * Qsum(rt[y],0,mxdep,0,dep[x] - 1);
} // x in anc(y)
void dfsMer(int x)
{
    for(auto y : Chg[x])
        modify(rt[x],0,mxdep,dep[y],1);
    for(auto y : G[x])
        dfsMer(y),rt[x] = Merge(rt[x],rt[y],0,mxdep);
}
Ans_t ans;
void divide(vector<int> &v,int l,int r,int ql,int qr)
{
	if(l > r || ql > qr) return;
	int mid = l + r >> 1,tmp = -1,k = 0;
	for(int i = ql;i <= min(qr,mid - 1);i++)
	{
		int val = calc(v[i],v[mid]);
		ckmax(ans,mkt(val,fa_id[v[i]],fa_id[v[mid]]));
		if(val > tmp) tmp = val,k = i;
	}
	divide(v,l,mid - 1,ql,k);
	divide(v,mid + 1,r,k,qr);
}
void Solve_c(vector<int> v)
{
    // printf("v: ");
    // for(auto it : v) printf("%d ",it);
    // printf("\n");
	sort(v.begin(),v.end(),[&](const int &x,const int &y) { return dep[x] < dep[y];});
	divide(v,0,v.size() - 1,0,v.size() - 1);
}
map<ull,vector<int> > cols;
void Clr()
{
	ect = 1;ans = mkt(-1,0,0);
	for(int i = 1;i <= n;i++)
	{
		fir[i] = hsh[i] = cov[i] = dep[i] = fa[i] = fa_id[i] = rt[i] = vis[i] = 0;
		G[i].clear();Chg[i].clear();
		sze[i] = son[i] = top[i] = 0;
	}
	for(int i = 1;i <= m;i++)
		intree[i] = 0;
	cols.clear();
	for(int i = 1;i <= tot;i++)
		lc[i] = rc[i] = sum[i] = 0;
	tot = 0;mxdep = 0;
	// dfstime = 0;
}
map<ull,int> hshvals;
vector<pii> bri;
void Work()
{
	read(n);read(m);Clr();
	for(int i = 1;i <= m;i++)
		read(U[i]),read(V[i]),addedge(U[i],V[i],i),addedge(V[i],U[i],i);
	dep[1] = 1;
	dfs0(1,0);
	dfs1(1);
	dfs2(1,1);
	hshvals.clear();
	bri.clear();
	for(int i = 1;i <= n;i++) ckmax(mxdep,dep[i]);
	for(int i = 1;i <= m;i++) if(!intree[i])
	{
		int u = U[i],v = V[i];
// 		printf("outtree:%d,%d\n",u,v);
		ull val = Rnd();hshvals[val] = i;
		hsh[u] ^= val;hsh[v] ^= val;
	}
	read(Q);
	for(int i = 1,u,v;i <= Q;i++)
	{
		read(u);read(v);
		int lc = lca(u,v);
		cov[u]++;cov[v]++;cov[lc] -= 2;
		Chg[v].push_back(lc);
		Chg[u].push_back(lc);
	}
	dfssum(1);
// 	printf("cov: ");for(int i = 1;i <= n;i++) printf("%d ",cov[i]);printf("\n");
	for(int i = 2;i <= n;i++)
		if(!hsh[i])
			bri.emplace_back(cov[i],fa_id[i]);
	// for(int i = 1;i <= m;i++)
	// 	if(cut[i]) bri.emplace_back(cov[nd_id[i]],i);
	sort(bri.begin(),bri.end(),greater<pii>());
	if(bri.size() == 1) ckmax(ans,mkt(bri[0].FI,bri[0].SE,bri[0].SE == 1 ? 2 : 1));
	else if(bri.size()) ckmax(ans,mkt(bri[0].FI + bri[1].FI,bri[0].SE,bri[1].SE));
//	return;
	for(int i = 1;i <= n;i++)
		if(hshvals.find(hsh[i]) != hshvals.end()) 
			ckmax(ans,mkt(cov[i],fa_id[i],hshvals[hsh[i]]));
	dfsMer(1);
	// dfsMer();
	for(int i = 1;i <= n;i++)
		if(hsh[i]) cols[hsh[i]].push_back(i);
	for(auto it : cols)
		Solve_c(it.SE);
	if(ans == mkt(-1,0,0))
		printf("0\n%d %d\n%d %d\n",U[1],V[1],U[2],V[2]);
	else
	{
		printf("%d\n",get<0>(ans));
		printf("%d %d\n",U[get<1>(ans)],V[get<1>(ans)]);
		printf("%d %d\n",U[get<2>(ans)],V[get<2>(ans)]);

	}
}

int main()
{
	int T;
	read(T);
	while(T--) Work();
	return 0;
}
≡