「2019-08-13 省常中互测」城镇

Description

每一次往一个图中加入一条边,然后查找在这条边连接的联通块中的直径是多少。

数据保证不会出现环状的图。

Data Range

$n\leq 3\times 10^5$。

Solution

考虑启发式合并。

对于两个联通块,我们就把$size$较小的合并到较大的中,这样就等价于每一次将问题变成一个小于二分之一的子问题,这样的复杂度为$O(log_2n)$

假设我们已经算出了两个联通块中的直径端点,一共有$4$个,分别标记为$p1,p2,p3,p4$。

那么合并这两个连通块后得到的直径端点就是$p1,p2,p3,p4$中的其中两个,也就是$6$种情况。

考虑这些节点的最大值,因为我们合并后得到的是一棵树,就合并后搜索较小的联通快,预处理出倍增数组,然后求出$lca$求出点与点之间的距离,然后取最大的就可以了。

代码细节较多。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 300000 + 5;

struct edge {
    int to, nt;
} E[N << 1];

int H[N], fa[N][25], dep[N];
int per[N], per_sz[N];
int n;

pair<int, int> nod[N];

int edge_cnt = 1, max_log;

void add_edge(int u, int v) {
    E[++ edge_cnt] = (edge) {v, H[u]};
    H[u] = edge_cnt;
}

int get_per(int x) {
    return per[x] == x ? x : per[x] = get_per(per[x]); 
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = max_log; i >= 0; i --) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    for (int i = max_log; i >= 0; i --) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; 
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void dfs(int u, int _fa) {
    fa[u][0] = _fa;
    dep[u] = dep[_fa] + 1;
    for (int i = 1; i <= max_log; i ++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int e = H[u]; e; e = E[e].nt) {
        int v = E[e].to;
        if (v == _fa) continue;
        dfs(v, u);
    }
}

int _dis(int u, int v) {
    int _lca = lca(u, v);
    return dep[u] + dep[v] - (dep[_lca] << 1);
}

int solve(int u, int v) {
    
    add_edge(u, v); 
    add_edge(v, u);
    
    int p1 = get_per(u), p2 = get_per(v);
    
    if (per_sz[p1] > per_sz[p2]) {
        swap(p1, p2);
        swap(u, v);
    }
    
    // u is smaller one
    
    dfs(u, v);
    
    int t1 = nod[p1].first, t2 = nod[p1].second, t3 = nod[p2].first, t4 = nod[p2].second;
    
    int dis1 = _dis(t1, t2), dis2 = _dis(t1, t3), dis3 = _dis(t1, t4);
    int dis4 = _dis(t2, t3), dis5 = _dis(t2, t4);
    int dis6 = _dis(t3, t4);   
     
    int __dis = 0, t01 = 0, t02 = 0;
    
    if (__dis < dis1) { __dis = dis1; t01 = t1; t02 = t2; }
    if (__dis < dis2) { __dis = dis2; t01 = t1; t02 = t3; }
    if (__dis < dis3) { __dis = dis3; t01 = t1; t02 = t4; }
    if (__dis < dis4) { __dis = dis4; t01 = t2; t02 = t3; }
    if (__dis < dis5) { __dis = dis5; t01 = t2; t02 = t4; }
    if (__dis < dis6) { __dis = dis6; t01 = t3; t02 = t4; }
    
    per[p1] = p2;
    per_sz[p2] += per_sz[p1];
    nod[p2] = make_pair(t01, t02); 
    return __dis;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i ++) {
        per[i] = i;
        per_sz[i] = 1;
        nod[i] = make_pair(i, i); 
        dep[i] = 0;
    }
    
    max_log = log2(n) + 1;
    
    for (int i = 1; i < n; i ++) {
        int u, v; 
        scanf("%d%d", &u, &v);
        printf("%d\n", solve(u, v));
    }
    return 0; 
}
最后修改:2019 年 08 月 24 日 08 : 54 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论