专栏首页ACM小冰成长之路51Nod-1618-树或非树

51Nod-1618-树或非树

ACM模版

描述

题解

这是 CFCF 上的一道原题,没有啥思路,于是找来一下题解,找到了一个远古的博客(jasonzhu8’s blog),里面有这个题的题解,然而他的代码写得实在让我难受,并且有一点我不是特别理解,但是依然是大佬。

大佬题解:

这个题解的第一句我无法理解,题目中说给定一个 nn 点 nn 边的无向图,可是并没有说是 一棵树 + 一条边 啊,这么强的条件,我不理解该大佬从何悟出,难道说是因为数据太水了,误打误撞的吗?这个问题我纠结了一天,怎么想也想不通为何得出这样的结论,当然,如果是建立在这个强条件下,那么后边的题解就很容易理解了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

int n, m;
int cnt1, cnt2, tmp, mb, mdb, ans;
int d[MAXN], z[MAXN], g[MAXN], o[MAXN];
int pre[MAXN], pre_[MAXN], p[MAXN << 1], nxt[MAXN << 1];

struct node
{
    int g, cnt;
    int l[MAXN], r[MAXN];
    int z[MAXN], a[MAXN];
    int x[MAXN], y[MAXN];
    int pre[MAXN], root[MAXN];

    void put(int i, int j)
    {
        if (i && j)
        {
            z[i] = !z[i];
            a[i] = !a[i];
            swap(x[i], y[i]);
        }
    }

    void lazy(int i)
    {
        put(l[i], z[i]);
        put(r[i], z[i]);
        z[i] = 0;
    }

    void rt(int i, int j)
    {
        if (l[i] == j)
        {
            l[i] = r[j];
            pre[r[j]] = i;
            r[j] = i;
        }
        else
        {
            r[i] = l[j];
            pre[l[j]] = i;
            l[j] = i;
        }
        root[j] = root[i];
        root[i] = 0;
        if (l[pre[i]] == i)
        {
            l[pre[i]] = j;
        }
        else if (r[pre[i]] == i)
        {
            r[pre[i]] = j;
        }

        pre[j] = pre[i];
        pre[i] = j;
        update(i);
        update(j);
    }

    void splay(int i, int j)
    {
        if (root[i])
        {
            lazy(i);
        }
        while (!root[i])
        {
            lazy(pre[i]);
            lazy(i);
            rt(pre[i], i);
        }
        if (j)
        {
            root[g = r[i]] = 1;
            r[i] = 0;
            update(i);
        }
    }

    void update(int i)
    {
        x[i] = x[l[i]] + x[r[i]] + a[i];
        y[i] = y[l[i]] + y[r[i]] + 1 - a[i];
    }

    void access(int i)
    {
        splay(cnt = i, 1);
        while (pre[i])
        {
            splay(cnt = pre[i], 1);
            r[cnt] = 1;
            rt(cnt, i);
        }
    }

    void cover(int i)
    {
        access(i);
        splay(tmp, 0);
        ans += y[r[tmp]] - x[r[tmp]];
        put(r[tmp], 1);
    }
} tree;

void link(int a, int b)
{
    nxt[++cnt1] = d[a];
    d[a] = cnt1;
    p[cnt1] = b;
}

int find(int i)
{
    return (pre_[i] == i) ? i : pre_[i] = find(pre_[i]);
}

void dfs1(int i, int h)
{
    z[++cnt1] = i;
    o[i] = cnt1;
    for (int k = d[i], j = p[k]; k; k = nxt[k], j = p[k])
    {
        if ((h ^ k) != 1)
        {
            if (o[j])
            {
                mb = k;
                for (int l = o[j]; l <= cnt1; l++)
                {
                    g[++cnt2] = z[l];
                }
            }
            else
            {
                dfs1(j, k);
            }
        }
    }
    cnt1--;
}

void dfs2(int i, int h)
{
    for (int k = d[i], j = p[k]; k; k = nxt[k], j = p[k])
    {
        if ((h ^ k) != 1 && ((k ^ mb) > 1))
        {
            pre[j] = i;
            dfs2(j, k);
        }
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scan_d(n);
    scan_d(m);

    cnt1 = 1;
    int a, b, mdb = 0;
    for (int i = 1; i <= n; i++)
    {
        scan_d(a);
        scan_d(b);
        link(a, b);
        link(b, a);
    }

    cnt1 = 0;
    dfs1(1, 0);
    dfs2(g[1], 0);
    for (int i = 0; i < MAXN; i++)
    {
        o[i] = 0;
    }
    for (int i = 1; i <= cnt2; i++)
    {
        o[g[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        pre_[i] = (o[i]) ? i : pre[i];
    }
    for (int i = 1; i <= n; i++)
    {
        find(i);
    }
    for (int i = 1; i <= n; i++)
    {
        tree.pre[i] = pre[i];
        tree.y[i] = tree.root[i] = 1;
    }

    g[0] = g[cnt2];
    tmp = g[cnt2 + 1] = g[1];
    while (m--)
    {
        scan_d(a);
        scan_d(b);
        int Fa = pre_[a], Fb = pre_[b];
        int d1 = abs(o[Fa] - o[Fb]);
        int g1, g2;
        if (o[Fa] < o[Fb])
        {
            g1 = g[o[Fa] + 1];
            g2 = g[o[Fa] - 1];
        }
        else
        {
            g1 = g[o[Fa] - 1];
            g2 = g[o[Fa] + 1];
        }

        tree.cover(a);
        tree.cover(b);
        if (d1 > cnt2 - d1 || ((d1 == cnt2 - d1) && g1 > g2))
        {
            mdb = !mdb;
            if (mdb)
            {
                ans++;
            }
            else
            {
                ans--;
            }
            tree.cover(g[cnt2]);
        }

        tree.access(g[cnt2]);
        int al = tree.x[g[cnt2]] + mdb == cnt2;

        printf("%d\n", n - ans + al);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 51Nod-1612-合法表达式

    ACM模版 描述 ? 题解 我们需要考虑到能够加多少括号以及加括号的动态规划过程,这里格外要注意一个问题,就是初始字符串不合法,并且无论怎么加都不合法的情况,比...

    f_zyj
  • HDU-5985-Lucky Coins

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • POJ-1961-Period

    ACM模版 描述 ? 题解 类似于 POJ-2406-Power Strings,不过这个题是要求处理所有的前缀的循环节,并且只输出循环节出现次数大于1 的前缀...

    f_zyj
  • 2018 蓝桥杯省赛 B 组模拟赛(五) B 结果填空:素数个数

    题目链接: https://nanti.jisuanke.com/t/25085

    Ch_Zaqdt
  • #633 DIV2 题解

    组样例,每组样例给一个, 代表个三角形按照菱形的样子尽可能的拼凑在一起(可以旋转),如图所示

    ACM算法日常
  • Android自定义gridView仿头条频道拖动管理功能

    项目中遇到这样个需求:app的功能导航需要可拖动排序,类似头条中的频道拖动管理。效果如下,gif不是很顺畅,真机会好很多。

    砸漏
  • 洛谷P2792 [JSOI2008]小店购物(最小树形图)

    一开始的思路:新建一个虚点向每个点连边,再加上题面中给出的边,边权均为大小*需要购买的数量

    attack
  • POJ 2594 Treasure Exploration(最小路径覆盖+Floyd)

           题意是有n个点,m条单向边,然后在边上放机器人,问最少放多少个机器人能遍历到所有的点。

    Ch_Zaqdt
  • 【POJ 2942】Knights of the Round Table(点双连通分量,二分图染色)

    在补图的一个奇圈里(由奇数个点组成的环)每个点都是可以参加的。而一个奇圈一定在点双连通分量里,所以我们把原图的每个点双连通分量找出来,然后判断是否有奇圈。用到了...

    饶文津
  • BZOJ2337: [HNOI2011]XOR和路径(期望 高斯消元)

    设\(f[i]\)表示从\(i\)到\(n\)边权为1的概率,统计答案的时候乘一下权值

    attack

扫码关注云+社区

领取腾讯云代金券