洛谷题单指南-连通性问题-P7737 [NOI2021] 庆典
原题链接：https://www.luogu.com.cn/problem/P7737
题意解读：在有向图中，有q个询问，求从s到t的路径上，可以借助k个临时边的情况下，一共可以经过多少个点，点可以重复走。
解题思路：
1、问题分析
点可以重复走，那么就应该先通过强联通分量进行缩点。
缩点后是DAG，题目还有一个重要的性质：对于三座城市 x，y，z，若 x⇒z 且 y⇒z，那么有 x⇒y 或 y⇒x。意味着如果从x有两条到z的路径，那么只需要保留一条，且不影响整个图的连通性，应该保留哪一条呢？答案是拓扑排序时，使其入度减为0的哪一条边，对此建立一棵树，更便于处理。
有了缩点后的DAG的生成树，还要处理临时边的问题，由于临时边不多，可以针对s、t以及所有临时边涉及的节点，建立虚树！虚树的点权值就是连通分量的大小，边权值就是两个缩点之间所有点权值之和。对于临时边，权值为0。
然后在虚树上，在正向图中从起点s BFS标记经过的点和边，在反向图中从终点t BFS标记经过点和边，对于交集的部分累加答案。
2、注意事项
关键点一：虚树的节点不多，不能沿用原图的节点号，这样会在每次memset邻接表数组时性能较慢，应该进行类似离散化处理，使得虚树节点编号从1开始，这样虚树邻接表头数组最长可以设置为30。
关键点二：q次询问，每次建立虚树的消耗在30*log(n)，log(n)是lca的复杂度，这样也是无法通过的，需要采用O(1)的LCA算法，这里使用欧拉序+ST表的方式，其核心原理就是记录dfs过程中每个时间戳对应的节点(回溯时也要记录)，对于lca(u,v)就是u、v欧拉序之间深度最小的节点，通过ST表维护区间深度最小的节点即可。
100分代码：
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
const int N = 300005, M = 2000005, V = 30;
//建图
int head1[N]; //原图
int head2[N]; //缩点图
int head3[N]; //拓扑排序生成叶向树
int head4[V]; //虚树-正向
int head5[V]; //虚树-反向
int to[M], w[M], nxt[M], idx;
//tarjan
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], sz[N], cnt;
int in[N];
int root;
int n, m, q, k;
void add(int head[], int a, int b, int c)
{
to[++idx] = b, w[idx] = c, nxt[idx] = head[a], head[a] = idx;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;
stk.push(u);
vis[u] = true;
for(int i = head1[u]; i; i = nxt[i])
{
int v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
while(true)
{
int t = stk.top(); stk.pop();
vis[t] = false;
scc[t] = cnt;
sz[cnt]++;
if(t == u) break;
}
}
}
void buildDAG()
{
for(int u = 1; u <= n; u++)
{
for(int i = head1[u]; i; i = nxt[i])
{
int v = to[i];
int a = scc[u], b = scc[v];
if(a != b)
{
add(head2, a, b, 0);
in[b]++;
}
}
}
}
void topsort()
{
queue<int> q;
for(int i = 1; i <= cnt; i++)
if(!in[i])
q.push(i);
while(q.size())
{
int u = q.front(); q.pop();
for(int i = head2[u]; i; i = nxt[i])
{
int v = to[i];
if(--in[v] == 0)
{
q.push(v);
add(head3, u, v, 0);
if(root == 0) root = u;
}
}
}
}
//LCA,路径和，DFN
int depth[N], sum[N], dfn2[N], timestamp2;
int id[N << 1], st[N << 1][20]; //欧拉序实现O(1) LCA
void dfs(int u, int p)
{
dfn2[u] = ++timestamp2; //记录DFN序
id[timestamp2] = u; //记录欧拉序对应的节点
depth[u] = depth[p] + 1;
sum[u] = sum[p] + sz[u];
for(int i = head3[u]; i; i = nxt[i])
{
int v = to[i];
if(v == p) continue;
dfs(v, u);
id[++timestamp2] = u; //记录欧拉序对应的节点
}
}
//st[i][j]表示欧拉序区间[i, i + 2^j - 1]的最小深度节点
void init()
{
for(int i = 1; i <= timestamp2; i++) st[i][0] = id[i];
for(int j = 1; j <= 19; j++)
{
for(int i = 1; i + (1 << j) - 1 <= timestamp2; i++)
{
int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
if(depth[a] < depth[b]) st[i][j] = a;
else st[i][j] = b;
}
}
}
//u和v的lca是区间[dfn2[u], dfn2[v]]的最小深度节点
int lca(int u, int v)
{
u = dfn2[u], v = dfn2[v];
if(u > v) swap(u, v);
int t = log2(v - u + 1);
int f1 = st[u][t], f2 = st[v - (1 << t) + 1][t];
return depth[f1] < depth[f2] ? f1 : f2;
}
//获取虚树节点编号
map<int, int> n2v, v2n;
int vid;
int getVNode(int x)
{
if(!n2v.count(x))
{
n2v[x] = ++vid;
v2n[vid] = x;
}
return n2v[x];
}
bool cmp(int x, int y)
{
return dfn2[x] < dfn2[y];
}
//构建虚树
int nodes[N], total;
void buildVTree()
{
sort(nodes + 1, nodes + total + 1, cmp);
int len = total;
for(int i = 1; i < len; i++)
{
int u = nodes[i], v = nodes[i + 1];
int l = lca(u, v);
nodes[++total] = l;
}
sort(nodes + 1, nodes + total + 1, cmp);
total = unique(nodes + 1, nodes + total + 1) - nodes - 1;
for(int i = 1; i < total; i++)
{
int u = nodes[i], v = nodes[i + 1];
int l = lca(u, v);
if(l == v) continue;
int distsum = sum[v] - sum[l] - sz[v];
add(head4, getVNode(l), getVNode(v), distsum), add(head5, getVNode(v), getVNode(l), distsum);
}
}
//双向BFS查找路径上的点数
bool vis1[V], edge1[V], edge2[V];
int find(int s, int t)
{
memset(vis1, 0, sizeof(vis1));
memset(edge1, 0, sizeof(edge1));
memset(edge2, 0, sizeof(edge2));
int res = 0;
queue<int> q;
//正向图中从起点s开始标记
q.push(s);
while(q.size())
{
int u = q.front(); q.pop();
vis1[u] = true;
for(int i = head4[u]; i; i = nxt[i])
{
int v = to[i];
if(!edge1[i])
{
q.push(v);
edge1[i] = true;
}
}
}
//反向图中从终点t开始标记，累加交集的个数
q.push(t);
while(q.size())
{
int u = q.front(); q.pop();
if(vis1[u]) //发现点交集
{
res += sz[v2n[u]];
vis1[u] = false;
}
for(int i = head5[u]; i; i = nxt[i])
{
int v = to[i];
if(!edge2[i])
{
q.push(v);
edge2[i] = true;
if(edge1[i - 1]) //发现边交集
{
res += w[i];
edge1[i - 1] = false;
}
}
}
}
return res;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> q >> k;
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(head1, u, v, 0);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
tarjan(i);
buildDAG(); //缩点
topsort(); //拓扑排序建立叶向树
dfs(root, 0); //预处理
init(); //初始化LCA
while(q--)
{
memset(head4, 0, sizeof(head4));
memset(head5, 0, sizeof(head5));
total = 0, idx = 0, vid = 0, n2v.clear(), v2n.clear();
int s, t;
cin >> s >> t;
s = scc[s], t = scc[t];
nodes[++total] = s;
nodes[++total] = t;
for(int i = 1; i <= k; i++)
{
int a, b;
cin >> a >> b;
a = scc[a], b = scc[b];
if(a == b) continue; //自环
nodes[++total] = a;
nodes[++total] = b;
add(head4, getVNode(a), getVNode(b), 0), add(head5, getVNode(b), getVNode(a), 0); //虚树中加0边
}
buildVTree(); //建立虚树其余边
cout<< find(getVNode(s), getVNode(t)) << endl; //找路径上的点数
}
return 0;
}