CF1935F 题解

sunkuangzheng · 2024-03-06 12:57:36 · 题解

\textbf{CF1935F *3000}

给定一棵树，对于 i \in [1,n] 求出以下问题的答案：

将点 i 及所有 i 相连的边删除后，定义一条连接 u,v 的额外边的边权是 |u-v|，额外边不能连接 i。

用额外边将除点 i 外的点重新连成一棵树，最小化边权和。

由于作者没有写按秩合并，以下并查集复杂度均视为 \mathcal O(\log n)。

假设我们在求解节点 i 的答案，断开 i 后考虑连通块的形态。

显然答案的下界是 d_i-1，d_i 即节点 i 的度数，能达到这个下界当且仅当每条边的权值都是 1。

我们先将所有边权为 1 的连接两个不连通子树的边连接，容易发现 [1,i-1] 和 [i+1,n] 中的节点已经各自连通。那么，如果存在一条树边 u,v 满足 u \in [1,i-1],v \in [i+1,n]，我们的答案就是 d_i-1。否则，我们直接连接 i-1,i+1，代价为 d_i-2+1=d_i。检验这个方法很多，这里提供复杂度较为优秀、实现简单的做法：判断是否存在一个连通块，使得 \min < i,\max > i。一个连通块形如一个子树，或是子树外的全部，那么 dfs 序配合 ST 表即可求 \min,\max，时间复杂度 \mathcal O(n \log n)- \mathcal O(1)。

当然这道题没有到这里结束，我们还需要给出构造，这也是本题的难点。

考虑如果直接暴力模拟上述过程，用并查集判断，复杂度将是 \mathcal O(n^2 \log n)，不可接受。

考虑设 mx_u,mn_u 表示 u 子树内的最大最小值（以 i 为根），边 (mx_u,mx_u+1) 和 (mn_u-1,mn_u) 一定连接了原树上两个不同的连通块，同时连接所有上述边后整张图连通，但是我们需要去除环。如果直接判断两个点是否在一个连通块里，就需要将树边先在并查集里合并，每次暴力合并复杂度还是会炸，此时可以线段树分治套可撤销并查集维护树边的连通性，然后再判断每条边是否需要加入即可，时间复杂度 \mathcal O(n \log^2 n)。

但是上面的做法太麻烦，事实上，我们连一条边只需要合并边的端点所在的子树，找到每个点所在的子树可以用 dfs 序上二分或者倍增，然后合并即可。总复杂度 \mathcal O(n \log n)。

/**
 *    author: sunkuangzheng
 *    created: 06.03.2024 09:58:50
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,u,v,dfn[N],cnt,nfd[N],siz[N],fa[N],mx[N],mn[N]; vector<int> g[N];
struct dsu{
    int fa[N];
    void init(int n){for(int i = 1;i <= n;i ++) fa[i] = i;}
    int fd(int x){return x == fa[x] ? x : fa[x] = fd(fa[x]);}
    bool mg(int x,int y){
        int fx = fd(x),fy = fd(y); 
        if(fx != fy) return fa[fx] = fy,1;
        else return 0;
    }
}d;
struct ST{
    int st[22][N],op;
    int cmp(int x,int y){return op ? max(x,y) : min(x,y);}
    void build(int _op,int *a){
        op = _op;
        for(int i = 1;i <= n;i ++) st[0][i] = a[i];
        for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            st[j][i] = cmp(st[j-1][i],st[j-1][i+(1<<j-1)]);
    }int qry(int l,int r){
        if(l > r) return (op ? 0 : 1e9);
        int k = __lg(r - l + 1);
        return cmp(st[k][l],st[k][r-(1<<k)+1]);
    }
}A,B;
void dfs(int u,int f){
    dfn[u] = ++cnt,nfd[cnt] = u,siz[u] = 1,fa[u] = f;
    for(int v : g[u]) if(v != f) dfs(v,u),siz[u] += siz[v];
}void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++) g[i].clear(); cnt = 0;
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    dfs(1,0),A.build(1,nfd),B.build(0,nfd);
    for(int i = 1;i <= n;i ++){
        if(g[i].size() == 1) {cout << "0 0\n";continue;} vector<int> fk,sb;
        int k = g[i].size(),ans = k - 1,fg = (i == 1 || i == n),ms = 1e9;
        auto ck = [&](int j){return mx[j] >= i && mn[j] <= i;};
        for(int j : g[i])
            if(j == fa[i]) mx[j] = max(A.qry(1,dfn[i]-1),A.qry(dfn[i]+siz[i],n)),
                           mn[j] = min(B.qry(1,dfn[i]-1),B.qry(dfn[i]+siz[i],n)),
                           fg |= ck(j),ms = dfn[i] + siz[i];
            else sb.push_back(dfn[j]),mx[j] = A.qry(dfn[j],dfn[j]+siz[j]-1),mn[j] = B.qry(dfn[j],dfn[j]+siz[j]-1),fg |= ck(j);
        if(!fg) ans ++; 
        cout << ans << " " << k - 1 << "\n"; 
        if(!fg) cout << i - 1 << " " << i + 1 << "\n";
        sort(sb.begin(),sb.end());
        auto get = [&](int x){
            if(x >= ms || x < sb.front()) return k;
            else return (int)(upper_bound(sb.begin(),sb.end(),x) - sb.begin());
        }; d.init(k);
        auto mg = [&](int x,int y){
            if(x != i && y != i && x >= 1 && y <= n) if(d.mg(get(dfn[x]),get(dfn[y]))) cout << x << " " << y << "\n";
        };
        for(int j : g[i]) mg(mn[j]-1,mn[j]),mg(mx[j],mx[j]+1);
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}