首页 > 代码库 > Codeforces Round #260 (Div. 1)——Civilization

Codeforces Round #260 (Div. 1)——Civilization

2024-07-17 03:14:13   223人阅读

题目链接

  • 题意：
    n个点，m条边的森林，q次操作。每次操作：1、询问x所在树的直径 2、合并x和y所在的树，使得合并后的直径最小
    (1?≤?n?≤?3·105; 0?≤?m?<?n; 1?≤?q?≤?3·105)
  • 分析：
    没有读到图是森林。。。做的好纠结
    最开始将每个树都求一下直径，之后使用并查集处理，每次合并直径：至少是两个树的直径，或者将两个直径的最中间的部分连接求直径
const int MAXN = 310000;

int rt[MAXN], ans[MAXN];
VI G[MAXN];
bool vis[MAXN];

void init(int n)
{
    REP(i, n)
    {
        vis[i] = false;
        ans[i] = 0;
        G[i].clear();
        rt[i] = i;
    }
}

int find(int n)
{
    return n == rt[n] ? n : rt[n] = find(rt[n]);
}

void merge(int a, int b)
{
    int fa = find(a), fb = find(b);
    if (fa != fb)
    {
        rt[fa] = fb;
        ans[fb] = max(ans[fb], (ans[fb] + 1) / 2 + (ans[fa] + 1) / 2 + 1);
        ans[fb] = max(ans[fa], ans[fb]);
    }
}

int Max, id;
void dfs(int u, int fa, int dep)
{
    vis[u] = true;
    REP(i, G[u].size())
    {
        int v = G[u][i];
        if (v != fa)
            dfs(v, u, dep + 1);
    }
    if (dep > Max)
    {
        Max = dep;
        id = u;
    }
}

int main()
{
    int n, m, q;
    while (~RIII(n, m, q))
    {
        init(n + 1);
        REP(i, m)
        {
            int a, b;
            RII(a, b);
            G[a].push_back(b);
            G[b].push_back(a);
            int fa = find(a), fb = find(b);
            rt[fa] = fb;
        }
        FE(i, 1, n)
        {
            if (!vis[i])
            {
                Max = -1;
                dfs(i, -1, 0);
                Max = -1;
                dfs(id, -1, 0);
                ans[find(i)] = Max;
            }
        }
        REP(i, q)
        {
            int op;
            RI(op);
            if (op == 2)
            {
                int a, b;
                RII(a, b);
                merge(a, b);
            }
            else
            {
                int a;
                RI(a);
                WI(ans[find(a)]);
            }
        }
    }
    return 0;
}


联系
我们