F. Edge Queries
https://codeforces.ml/contest/1763/problem/F
题意
n个点m条边的无向图,保证一个点不会存在多个连通分量中,q次询问,问对于从u到v的所有路径上的边,删掉一条边不影响u和v的连通性,问这样的边有多少条
思路
先进行边双缩点,因为在在同一个连通分量中的两个点至少存在两条路径。
那么容易得到,答案差不多就是u, v所在缩点之间的路径上所有连通分量的大小和(该大小指的是连通分量的边数)。
求一条路径上所有点的权值和
我们可以缩完点后建棵树 然后dfs求得每个点到根节点路径上的点权和 在用lca求即可
但还需要注意很多细节:
1.设a, b, c为u到v的路径上连续的三个连通分量,如果a和c连在b中的同一节点,那么b的大小不能被算进来
对于判断两个连通分量是否连接于同一节点 我们可以记录每个连通分量连向父亲的边的两个端点来做比较
2.考虑u和v恰好是连通分量的连接点,那么u和v所在的那个连通分量也不能被算进来
3.考虑求u, v的lca后,连在lca那个连通分量的同一个点 那么lca的大小不能被算进来
4.考虑特判 u == v和u, v在同一连通分量的情况
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const ll mod = 1e9 + 7;
int n, m;
int low[N], dfn[N], tot, ec, c[N], sz[N], val[N];
int uu[N], vv[N];
pair<int, int>edge[N];
vector<int>g[N], g2[N];
stack<int>st;
//边双缩点
void tarjan(int x, int fa){
dfn[x] = low[x] = ++tot;
st.push(x);
for(auto to : g[x]){
if(!dfn[to]) {
tarjan(to, x);
low[x] = min(low[to], low[x]);
}
else if(to != fa)
low[x] = min(low[x], dfn[to]);
}
if(dfn[x] == low[x]){
ec++;
while(1){
int now = st.top();
st.pop();
c[now] = ec;
if(now == x) break;
}
}
}
void init(){
for(int i = 1; i <= n; i++){
g[i].clear();
g2[i].clear();
low[i] = dfn[i] = 0;
c[i] = 0;
sz[i] = 0;
val[i] = 0;
}
ec = 0;
tot = 0;
}
//求LCA板子
ll fa[N][32], dep[N];
void dfs(ll x, ll pre, ll d)//找到每个节点父亲与深度
{
fa[x][0] = pre;
dep[x] = d;
for (auto to : g2[x]){
if (to != pre)
dfs(to, x, d + 1);
}
}
ll LCA(ll u, ll v)
{
if (dep[u] > dep[v])
swap(u, v);
ll temp = dep[v] - dep[u];
//cerr << "?" << v << " " << ans << "\n";
for (ll i = 0; ((1ll << i) <= temp); i++)//将u v移到同一深度
{
if ((1ll << i) & temp){
v = fa[v][i];
//cerr << "?" << v << " " << ans << "\n";
}
}
if (u == v)
return u;
for (ll i = log2(ec); i >= 0; i--)//两个节点一起往上走
{ //最多合法的跳跃是 2 ^ log2(n)
if (fa[u][i] != fa[v][i])//如果相同则代表跳的太多了
{
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
void init2()
{
dfs(1, -1, 0);
for (ll j = 0; (1ll << j) <= ec; j++)//预处理出每个节点往上走2^j所到的节点,超过根节点记为-1
{
for (ll i = 1; i <= ec; i++)
{
if (fa[i][j] < 0){
fa[i][j + 1] = -1;
}
else {
fa[i][j + 1] = fa[fa[i][j]][j];
}
}
}
}
//求每个连通分量到根的路径上所有连通分量的大小和
void dfs_val(int x, int fa){
val[x] = sz[x];
if(fa > 0){
val[x] += val[fa];
if(uu[x] == vv[fa])
val[x] -= sz[fa];
}
for(auto to : g2[x]){
if(to == fa) continue;
dfs_val(to, x);
}
}
//找到某个点祖先的儿子
int get_secfa(int x, int d){
for(int i = 31; i >= 0; i--){
if((1ll << i) & d)
x = fa[x][i];
}
return x;
}
void solve()
{
cin >> n >> m;
init();
for(int i = 1, u, v; i <= m; i++){
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edge[i] = {u, v};
}
tarjan(1, -1);
// cerr << "???";
// for(int i = 1; i <= n; i++)
// cerr << c[i] << " ";
// cout << "\n\n";
for(int i = 1; i <= m; i++){
int u = edge[i].first;
int v = edge[i].second;
if(c[u] == c[v]) sz[c[u]]++;
else {
g2[c[u]].push_back(c[v]);
g2[c[v]].push_back(c[u]);
}
}
init2();
//求每个连通分量联想父亲的边的两个节点 uu vv
for(int i = 1; i <= m; i++){
int u = edge[i].first;
int v = edge[i].second;
if(c[u] != c[v]){
int fu = c[u];
int fv = c[v];
if(dep[fu] > dep[fv]) {
swap(fu, fv);
swap(u, v);
}
uu[fv] = u;
vv[fv] = v;
}
}
dfs_val(1, -1);
// for(int i = 1; i <= n; i++)
// cerr << sz[i] << " ";
int q;
cin >> q;
for(int i = 1; i <= q; i++){
int a, b, x, y;
cin >> x >> y;
if(x == y){
cout << 0 << "\n";
continue;
}
a = c[x];
b = c[y];
if(a == b) cout << sz[a] << "\n";
else {
int ans = 0;
if(dep[a] > dep[b]) {
swap(a, b);
swap(x, y);
}
int lc = LCA(a, b);
if(lc == a){
ans = val[b] - val[a] + sz[a];
int dis = dep[b] - dep[a] - 1;
int secfa = get_secfa(b, dis);
//情况1
if(uu[secfa] == vv[lc]) ans += sz[lc];
//情况2
if(vv[b] == y) ans -= sz[b];
if(uu[secfa] == x) ans -= sz[a];
}
else{
ans = val[a] + val[b] - val[lc] * 2 + sz[lc];
int dis1 = dep[a] - dep[lc] - 1;
int dis2 = dep[b] - dep[lc] - 1;
int secfa1 = get_secfa(a, dis1);
int secfa2 = get_secfa(b, dis2);
//情况1
if(uu[secfa1] == vv[lc]) ans += sz[lc];
if(uu[secfa2] == vv[lc]) ans += sz[lc];
//情况3
if(uu[secfa1] == uu[secfa2]) ans -= sz[lc];
//情况2
if(vv[a] == x) ans -= sz[a];
if(vv[b] == y) ans -= sz[b];
}
cout << ans << "\n";
}
}
}
signed main()
{
IOS;
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
}
标签:sz,lc,val,fa,cf1763,int,Edge,Queries,dep
From: https://www.cnblogs.com/yaqu-qxyq/p/17003781.html