url: https://www.luogu.com.cn/problem/P2195

tag:
树的直径，树形DP，dfs，搜索，并查集，图论

思路：
先用树形DP求出每棵树的直径，并用并查集维护联通情况。用数组c来维护树的直径。对于询问1，直接输出直径，对于询问2，如果不在一个集合中，直径可能是原来两棵树的直径和 + 1，和原来两棵树的直径取一个最大值。参考： https://www.luogu.com.cn/article/o2yhg6cs

代码：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 3e5 + 20;
int n, m, q, len;
int d[N], g[N];
int f[N], c[N];
vector<int> e[N];
bool st[N];
int find(int x)
{
    if (f[x] != x) return f[x] = find(f[x]);
    return x;
}
void dfs(int x, int fa)
{
    int m1 = -1, m2 = -1;
    for (int i = 0; i < e[x].size(); i ++)
    {
        int y = e[x][i];
        if (y == fa) continue;
        dfs(y, x);
        int tmp = d[y] + 1;
        d[x] = max(d[x], tmp);
        if (tmp > m1) m2 = m1, m1 = tmp;
        else if (tmp > m2) m2 = tmp;
    }
    g[x] = max(max(0, m1 + m2), max(m1, m2));
    len = max(len, g[x]);
}
void calc(int x)
{
    len = 0;
    dfs(x, 0);
    c[x] = len;
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++) f[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        f[find(a)] = find(b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] != i || st[i]) continue;
        calc(i);
        st[i] = 1;
    }
    while (q --)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            printf("%d\n", c[find(x)]);
            continue;
        }
        int y;
        scanf("%d", &y);
        x = find(x), y = find(y);
        if (x == y) continue;
        int tmp = ((c[x] + 1) >> 1) + ((c[y] + 1) >> 1) + 1;
        tmp = max(tmp, max(c[x], c[y]));
        f[find(x)] = find(y);
        c[find(x)] = tmp;
    }
    return 0;
}

url: https://www.luogu.com.cn/problem/P1111

tag:
kruskal算法, 并查集

思路：
先按照边权排序，然后依次取出每条边，判断两个点是否联通（是否在一个集合）如果不连通就加一条边，然后更新下res = max(res, w) 然后边数++，最后判断边数是否为点个数-1，表示所有点都连上，如果没有则输出-1，否则输出res

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
struct edg {
    int x, y, t;
} Edg[N];
bool cmp(edg &a, edg &b)
{
    return a.t < b.t;
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> Edg[i].x >> Edg[i].y >> Edg[i].t;
    }
    sort(Edg + 1, Edg + m + 1, cmp);
    for (int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        int a = find(Edg[i].x), b = find(Edg[i].y), w = Edg[i].t;
        if (a != b)
        {
            p[a] = b;
            res = max(res, w);
            cnt ++;
        }
    }
    if (cnt < n - 1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}