「树的直径 + 并查集」HXY造公园

HXY造公园

题目大意

给你三个数 (n, m, q) 代表一棵树有(n)个节点，再给你(m)行，每行两个数(u, v)，代表(u, v)间有一条无向边，然后再给你(q)行，每行代表一个操作，第一个数如果是 1，则再输入一个数，表示查询当前点所在树的直径大小，第一个数如果是 2，则再输入两个数(x, y)，表示查询在(x, y)所在树连接起来后的直径最大值最小是多少。

题目题解

很简单的题，刚看题的时候语文不太好甚至没读懂，看了下题解瞬间理解了

首先是第一个操作，考虑用并查集固定每个树的根节点，然后用树的直径算出每次以哪个根节点为起点的树的直径，每次查找只需要返回根节点就可以了

第二次操作也很简单，首先考虑一种情况就是，最大值最小，我们知道，如果两个树相连，那么两个树各一半的子树都会形成一条链，然后两两配对，怎么让其链长度最小？只需要让原一棵的树的直径/2就可以得到我们的最小链了，那么连接还需要一个长度。只有这样还不够，我们还能知道，如果连接后的链还不如其中一棵树的直径长度，那么我们两两配对的链组成的就不是我们的直径了，我们还需要和两个树原有的直径进行比较，到此完毕。（推导公式详细看代码，懒得写了..）

代码如下（

//#define fre yes

#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 300005;
int head[N << 1], to[N << 1], ver[N << 1];
int par[N];
int d[N], ans[N];
bool Vis1[N], Vis2[N];

int tot;
void addedge(int x, int y) {
    ver[tot] = y;
    to[tot] = head[x];
    head[x] = tot++;
}

void init(int n) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
}

int find(int x) {
    if(par[x] == x) return par[x];
    else return par[x] = find(par[x]);
}

void unite(int x, int y) {
    int a = find(x);
    int b = find(y);
    if(a == b) return ;

    par[a] = b;
}

int maxx, st;
void dfs1(int x, int val) {
    if(maxx < val) maxx = val, st = x;
    for (int i = head[x]; ~i; i = to[i]) {
        int v = ver[i];
        if(!Vis1[v]) {
            Vis1[v] = true;
            dfs1(v, val + 1);
        }
    } Vis1[x] = false;
}

void dfs2(int x, int val) {
    if(maxx < val) maxx = val;
    for (int i = head[x]; ~i; i = to[i]) {
        int v = ver[i];
        if(!Vis1[v]) {
            Vis1[v] = true;
            dfs2(v, val + 1);
        }
    } Vis1[x] = false;
}

void diameter(int n) {
    int ct = 0;
    for (int i = 1; i <= n; i++) {
        int x = find(i);
        maxx = -1;
        if(Vis2[x]) continue;
        Vis1[x] = true;
        dfs1(x, 0);

        Vis1[st] = true;
        maxx = -1;
        dfs2(st, 0);
        Vis2[x] = true;
        ans[x] = maxx;
    }
}

int main() {
    memset(head, -1, sizeof(head));
    static int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    init(n);
    for (int i = 1; i <= n; i++) d[i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        unite(u, v);
        addedge(u, v);
        addedge(v, u);
    }

    diameter(n);

    for (int i = 1; i <= q; i++) {
        int k;
        scanf("%d", &k);
        if(k == 1) {
            int x;
            scanf("%d", &x);
            printf("%d
", ans[find(x)]);
        }
        if(k == 2) {
            int u, v;
            scanf("%d %d", &u, &v);
            int x = find(u);
            int y = find(v);
            if(x == y) continue;
            par[x] = y;
            ans[y] = std::max(std::max((ans[x] + 1) / 2 + (ans[y] + 1) / 2 + 1, ans[x]), ans[y]);
        }
    } return 0;
}

这道题看了题解好像是卡memset，那就递归的时候同时解决吧