把几个错误的想法拼起来就可以AC啦

人生成就达成: hack了学姐的程序 和辣文第二谈笑风生 向BZOJ丢了一组数据

qwq

Info:这道题网上许多题解都是假的, 这道题确实可以只用并查集做到$\mathrm O(n)$

Warning: 写这篇题解的时候宽嫂有点激动…有一些奇怪的吐槽大家可以自动忽略 XD

惊奇的发现舒老师在两天前过了这题 虽然加强数据后被卡到9.5s差点没过 舒老师太强啦Orzzz

懵逼的 题目

qwqwq

扯淡的 题解

混乱的 思路

下面是想题时候的碎碎念…其实就是一堆吐槽 不看也罢

(昊哥给我丢了一道思(维)博(学)题, 昊哥已经确定这个题是并查集并且是要求$\mathrm O(n)$的做法)

树剖是$\mathrm O(n \lg^2 n)$的…被昊哥喷

如果我倒着做…好像没什么用…确定哪些点受影响好像还是$\mathrm O(n \lg^2 n)$的…

如果我把白边缩起来, 这样每一个点的祖先就是离他最近的黑边了吧?

  • 修改就GG了吧…

如果我把黑边缩起来, 这样修改的总复杂度是$\mathrm O(n)$的吧?

  • 查询也GG了啊…不能路径压缩…

然后一晚上就过去了…

第二天…

如果…我 把白边黑边分别缩起来…

然后…缩黑边的时候顺便把白边的fa设成自己…

  • 但是….不能路径压缩??????????

GG

Emmmmmmmmmmmmmmmmmmmmmmmm….

我如果倒过来…先把修改全部修改完, 然后再撤销, 是不是就可以路径压缩了??? (下面把边化成了点)

  • 把黑点的并查集都初始化为自己, 白点的并查集初始化为自己的父亲
  • 修改, 沿着黑边跑到LCA(要路径压缩), 把经过节点对应的白点并查集的fa设成他自己, 记录哪些节点受到了变化(用vector<int>[])
  • 查询, 直接在白点的并查集上查询祖先即可
  • 撤销, 把当前操作的vector<int>中的节点的白点并查集的fa都变成他自己的父亲即可

复杂度$\mathrm O(n\lg n)$然后没过(应该是倍增LCA太慢了)…

昊哥把网上的$n^2$暴力交上去A了, 比$sunshine$学长写的$\mathrm O(n)$正解还快$3s$…

十分愤怒, 遂生成数据卡之

生成完数据, 发现HXY学姐的正解没过

我格式错了???

然后YCR大佬发现…HXY学姐写了个假的正解…是个假的$\mathrm O(n)$…

遂找ZFF学长的代码, 过了, 遂联系辣文第二卡之

中午回家的时候突然想到, 如果我不找LCA, 而是一遍向上跳一边缩点, 然后每次都沿着并查集的边而非原树中的边跳, 就是$\mathrm O(n)$的了…

中午写了一发, 过了 跑的比ZFF学长快2s XD

Emmmmmmmm….

正了八经的 解释

上面那些都是吐槽, 不看也罢

这个题的思路就是:

既然修改的复杂度高, 就给他路径压缩; 既然查询的复杂度高, 那就也给他路径压缩; 白边黑边放在一起不好压缩, 就分别到两个并查集压缩; 每次黑边都可能向下延伸, 查询如果路径压缩可能GG, 那就把查询先做完, 每次撤销, 这样黑边的范围就可以从下到上, 可以路径压缩了

  • 我们发现, 染黑边, 其实就是染黑这条边的儿子, 这样我们就可以用黑点白点来做了
  • 搞两个并查集fb[], fw[], 分别用于 优化修改的复杂度 和 优化查询的复杂度, 初始的时候把他们成他们的父亲节点(即原树的结构)
  • 先把所有的修改都进行一遍, 每次修改的时候, 沿着并查集fb[]一个一个地向上跳, 把每一个跳到的节点的fw都赋成自己(然后记录这次修改有哪些白点发生了变化), 并黑点的并查集fb路径压缩
  • 倒着处理, 撤销修改, 每次撤销修改的时候就是把 那次修改被影响到的白点的并查集fw[x]的值设为他自己x
  • 查询的时候就是普通的并查集找祖先, 并且可以路径压缩

一些解释

  • 为什么要倒着做(正着做为什么不能路径压缩)?

1

如上图, 我要查询红色的点, 查询完毕, 路径压缩后会变成下面的情况

2

然后这时, 我在蓝色的地方加入一条黑边, 你就GG了…

而倒着处理, 黑色的边只会从下退至树根, 路径压缩过的边中肯定不会再有黑边出现了…

  • 为什么要一步步的沿着并查集的边跳?

直接求LCA是$\mathrm O(\lg n)$的…会被毒瘤出题人卡掉…但是沿着并查集的边向上跳并且一路路径压缩的话, 总复杂度是$\mathrm O(n)$的(每条边只会被经过/压缩一次)…这个点子其实来自当年的HardChoise

还是挺妙的 对吧?

沙茶的 代码

这道题其实有一个翻车点, 就是在用LCA的做法做的时候, 会出现LCA已经在当前黑点组成的并查集里了, 再跳的时候会超过LCA…然后就RE了…

所以我们要判断if (deep[dq] <= deep[lca]) return ;而不是if (dq == lca) return ;

/**************************************************************
    Problem: 3319
    User: Cansult
    Language: C++
    Result: Accepted
    Time:6404 ms
    Memory:96492 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (1000000 + 5)
#define MAXL (20 + 5)
#define rint register int 
#define cint const int 
using namespace std;
struct edg
{
    int from, to, next, bh;
}b[MAXN << 1];
int g[MAXN], fb[MAXN], fw[MAXN], fae[MAXN], n, q, d[MAXN], lgn, cntb, que[MAXN], deep[MAXN];
vector<int> xg[MAXN], ans;
inline void adn(cint from, cint to, cint bh)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].bh = bh;
    g[from] = cntb;
}
int lg(cint x)
{
    int re = 0;
    while ((1 << re) <= x)
        ++re;
    return re;
}
int chan(int x, int y, cint bh)
{
    if (x == y)
        return x;
    if (deep[x] < deep[y])
        swap(x, y);
    if (fw[x] != x)
        xg[bh].push_back(x);
    fw[x] = x;
    return (fb[x] = chan(fb[x], y, bh));
}
void dfs(int dq, int de)
{
    deep[dq] = de;
    for (int i = g[dq]; i; i = b[i].next)
        if (b[i].to != d[dq])
            fae[b[i].to] = b[i].bh, d[b[i].to] = dq, dfs(b[i].to, de + 1);
}
int find(cint x)
{ return (x == fw[x] ? x : (fw[x] = find(fw[x]))); }
inline int read()
{
    rint re = 0;
    register char x = 0;
    while (x < '0' || x > '9')
        x = getchar();
    while (x <= '9' && x >= '0')
        re = (re << 1) + (re << 3) + x - '0', x = getchar();
    return re;
}
int main()
{
    // scanf("%d%d", &n, &q);
    n = read(), q = read();
    lgn = lg(n);
    for (rint i = 1, srx, sry; i < n; i++)
    {
        // scanf("%d%d", &srx, &sry);
        srx = read(), sry = read();
        adn(srx, sry, i);
        adn(sry, srx, i);
    }
    d[1] = 1, fae[1] = 0;
    dfs(1, 1);
//  puts("ok");
    for (rint i = 1; i <= n; i++)
        fb[i] = fw[i] = d[i];
    for (rint i = 1, sre, srx, sry; i <= q; i++)
    {
        // scanf("%d", &sre);
        sre = read();
        if (sre == 1)
            // scanf("%d", &que[i]);
            que[i] = read();
        else
        {
            // scanf("%d%d", &srx, &sry);
            srx = read(), sry = read();
            chan(srx, sry, i);
        }
//      printf("%d\n", i);
    }
//  puts("ok");
    for (rint i = q; i >= 1; i--)
    {
        for (rint j = 0; j < xg[i].size(); j++)
            fw[xg[i][j]] = d[xg[i][j]];
        if (que[i])
            ans.push_back(fae[find(que[i])]);
    }
    for (rint i = ans.size() - 1; i >= 0; i--)
        printf("%d\n", ans[i]);
    return 0;
}

By 不用月考的 Cansult