Codeforces Round #260 (Div. 1)—

题意：

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;

}

巴特西

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

最新文章

热门文章