60分代码求调
查看原帖
60分代码求调
558833
__Floze3__楼主2023/10/20 16:25
#include <bits/stdc++.h>
#define _FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define _FRO(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
using namespace std;
typedef long long ll;
typedef double db;

const int maxn = 3e5 + 5;

struct edge{
    int v, nxt;
}e[maxn << 1];

int n, m, q, fa[maxn], head[maxn], cnt, d1[maxn], d2[maxn], fl, d[maxn];

void dfs(int u, int fa){
    d1[u] = d2[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa) continue;
        dfs(v, u);
        int t = d1[v] + 1;
        if (t > d1[u]){
            d2[u] = d1[u];
            d1[u] = t;
        }
        else if (t > d2[u]) d2[u] = t;
    }
    fl = max(fl, max(max(0, d1[u] + d2[u]), d1[u] + d2[u]));
    return ;
}

void calc(int x){
    fl = 0;
    dfs(x, 0);
    // cout << fl << endl;
    d[x] = fl;
    return ;
}

inline void add(int u, int v){
    e[++cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
    return ;
}

inline void init(){
    _FOR(i, 1, n) fa[i] = i;
    return ;
}

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
    return ;
}

int main(){
    cin >> n >> m >> q;
    init();
    _FOR(i, 1, m){
        int x, y;
        cin >> x >> y;
        merge(x, y);
        add(x, y);
        add(y, x);
    }
    _FOR(i, 1, n){
        // cout << fa[i] << endl;
        if (fa[i] == i) calc(i);
    }
    while(q--){
        int opt;
        cin >> opt;
        if (opt == 1){
            int x;
            cin >> x;
            cout << d[find(x)] << endl;
        }
        else{
            int x, y;
            cin >> x >> y;
            x = find(x), y = find(y);
            int tmp = (((d[x] + 1) >> 1) + ((d[y] + 1) >> 1)) + 1;
            // cout << d[x] << ' ' << d[y] << endl;
            tmp = max(tmp, max(d[x], d[y]));
            // cout << tmp << endl;
            // cout << x << ' ' << find(x) << ' ' << y << ' ' << find(y) << endl;
            fa[x] = y;
            d[y] = tmp;
        }
    }
    return 0;
}
2023/10/20 16:25
加载中...