题解：AT_agc033_f [AGC033F] Adding Edges

· · 题解

先看若最终图上存在边 (u,v) 的充要条件，即存在一条 T 上的路径 P，使得存在一个点序列 x_{1\sim k},x_1=u,x_k=v，一开始存在边 (x_i,x_{i+1})\in G，且 x 中的点都在 P 上。

这个条件是比较烦人的，因为你没有限制 x_i 在 P 中的顺序，他可以到处乱窜。

假设限制了 x_i 必须在 P 中一次出现，我们枚举根 u，在 T 上 dfs，就可以得到最终图上的 deg_u。

考虑若我们转化出一个图 G'，使得在这个图上有限制的做等价于原问题，那么不就可以了吗。

若 T 中存在一个依次包含 x,y,z 的路径，且 (x,y),(x,z)\in G，那么把 (x,z) 替换为 (y,z) 也是等价的。

这样不断的做，最后就可以得到我们想要的图 G'。

如何实现呢？考虑每次加入边 (u,v)，动态的维护 G'。

若存在边 (u,v)，或者 P(u,v) 上不存在点 x，使得存在边 (u,x)/(v,x)，那么直接加入即可。

反之找到第一个这样的 x，递归入加入边 (v,x)/(u,x) 的子问题即可。

如何找到呢？设 f_{rt,u} 表示在根为 rt 的时候，u 最近的一个和根有连边的祖先。

每次真的可以加入 (u,v) 的时候，在 rt=u/rt=v 的情况下去更新子树内的信息即可，dfs 过程中若遇到了一个点 x，使得 (x,rt) 存在边，我们再递归的尝试加入 (x,v/u) 即可。

时间复杂度是多少？除去加边的过程，其他地方都是好分析的。

而加边的时候，若 f_{rt,u}=0，我们会直接赋值；反之我们相当于会把一条边剪断一部分后再加入。

那么复杂度就是 \mathcal{O}(n(n+m)) 的。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=2005,INF=0x3f3f3f3f;
int fa[N][N],f[N][N],n,m;
vector<int> G[N];
void init(int u,int dad,int rt){
    fa[rt][u]=dad;
    for(auto v : G[u]) if(v^dad)init(v,u,rt);
}
queue<pii> q;
void dfs(int u,int rt,int x){
    if(f[rt][u]) return q.push(m_p(u,x)),void(0);
    f[rt][u]=x;
    for(auto v : G[u]) if(v^fa[rt][u]) dfs(v,rt,x);
}
void ins(int x,int y){
    q.push(m_p(x,y));
    while(!q.empty()){
        auto [u,v]=q.front();q.pop();
        if(f[u][v]==v) continue;
        if(f[u][v]){q.push(m_p(f[u][v],v));continue;}
        if(f[v][u]){q.push(m_p(f[v][u],u));continue;}
        dfs(v,u,v),dfs(u,v,u);
    }
}
int ans;
void DFS(int u,int rt,int las){
    if(u!=rt&&f[u][las]==las) ans++,las=u;
    for(auto v : G[u]) if(v^fa[rt][u]) DFS(v,rt,las);
}
int main(){
    n=rd(),m=rd();
    for(int i=1,u,v;i<n;i++)u=rd(),v=rd(),G[u].p_b(v),G[v].p_b(u);
    for(int i=1;i<=n;i++)init(i,0,i);
    for(int i=1;i<=m;i++) ins(rd(),rd());
    for(int i=1;i<=n;i++)DFS(i,i,i);
    printf("%d\n",ans>>1);
    return 0;
}