不知为何 连烤 咕掉了......
这是一道性质题,猜个结论感觉还是蛮对的。

Description

Tgopknight 玩游戏玩的正开心时,屏幕上出现了一行 Connection Lost, Tgopknight 十分不高兴

Tgopknight 所连接的网络共有n个站点,由于经费问题,每两个站点之间有且仅有一条线路,这些站点中有一些损坏了, Tgopknigh 进行了 kk 次测试,每次测试两个站点之间是否连通,由于 Tgopknight 手气太好,他每次测试的两个站点之间都不连通。

Tgopknight 现在想知道最少有多少个站点损坏了,并想知道一种可能的损坏数最小的损坏情况。

Input

第一行输入两个正整数 n,mn,m,表示站点个数和直接连接数。 后接 mm 行,每行输入两个数 uu,表示 u,vu,v 直接连接。

m+2m+2 行输入一个正整数 kk, 表示 Tgopknight 进行的测试次数。 后接 kk 行,每行输入两个数 u,vu,v, 表示 Tgopknight 测试 u,vu,v 之间是否连通。

Output

第一行输出一个整数 ans ,表示最少损坏的站点数。

后接一行 ans 个数,表示一种可能的损坏情况。

Solution

想想要输出一种方案,做法很可能是贪心。我们观察到一个性质,删除的点为每次测试点对的 lca 一定是最优的。

O(n logn)O(n~logn)

因为深度深的 lca 删除后可能会连带着 lca 为深度浅的点对不连通,所以我们考虑深度从大到小删除点对的 lca。维护每个 lca 还有多少 lca 为自己的点对,若为 0 那么就不必删除该点。具体操作就是每删除一个点,遍历一遍子树,对子树中的点进行维护。

O(n log2n)O(n~log^{2}n)

同上操作,对于删除,我们可以用树链剖分维护路径和。那么就变成了一个单点修改,区间查询的问题。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, m, T, f[300005][21], dep[300005];
vector<int> d[300005], R[300005], ans;
struct Q {
int u,v,lca,vis;
bool operator < (const Q &rhs)const{return dep[lca]>dep[rhs.lca];}
}q[300005];
int b[300005], w[300005];

void dfs(int u,int fa=0) {for(int v:d[u])if(v!=fa){dep[v]=dep[u]+1,*f[v]=u,dfs(v,u);}}
int lca(int x,int y) {
if(dep[x]<dep[y])swap(x,y);
for(int i=20;~i;--i)
if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y) return x;
for(int i=20;~i;--i)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return *f[x];
}
void DFS(int u, int fa) {
if(b[u]) return;
for(int i:R[u])if(!q[i].vis){q[i].vis=1,w[q[i].lca]--;}
for(int v:d[u])if(v!=fa)DFS(v,u);
}

int main() {
freopen("ping.in","r",stdin);
freopen("ping.out","w",stdout);
read(n),read(m);
int u, v;
while(m--) {
read(u),read(v);
d[u].push_back(v), d[v].push_back(u);
}
dep[1]=1; dfs(1); rep(i,1,20)rep(x,1,n)f[x][i]=f[f[x][i-1]][i-1];
read(T);
rep(i,1,T) read(q[i].u),read(q[i].v),q[i].lca=lca(q[i].u,q[i].v),w[q[i].lca]++;
sort(q+1, q+T+1);
rep(i,1,T) R[q[i].u].push_back(i),R[q[i].v].push_back(i);
rep(i,1,T) {
if(!w[q[i].lca]) continue;
DFS(q[i].lca,*f[q[i].lca]); b[q[i].lca]=1;
ans.push_back(q[i].lca);
}
printf("%d\n", ans.size());
for(int x:ans) printf("%d ", x);
return ~~(0^_^0);
}