紫题算法学习实况

quest_2 · 2020-10-19 20:07:42 · 个人记录

因为进不去复赛就只能休养休养生息，整点算法学学。

和同机房的神仙相比，窝挖的坑实在是太多了 OvO 。

2020-10-21：竟然与he老爷讲课撞车了，两相对比显然突出窝的菜

2020-11-16：CSP-S又垫底了，可以安心写博客力

2020-12-26：该文章已停更，光标几乎卡的动不了了

《实况一》（本文）中包含的内容：

• 点分治

• 点分树

• fhq

• 网络流

• 杜教筛

点分治

“每天就是切一些 N 倍经验题，维持维持生活这样子。”

处理什么问题：

大部分是树上点对距离问题，当然还有一些变形。（树论毒瘤爪巴）

如果给您一棵树，让您查询树上是否存在两点距离为 K 。您没学过点分治，您怎么做？

您说，您会暴力 O(n^2) 枚举点对查询其距离！

抱歉，点分治是可以 O(n\log n) 的。

思想是什么：

现在讲一下思想。

树上两点之间，路径唯一 ，两点通向LCA的路径的并，即为两点之间的路径。

这种路径要分类无非两种：过 全树的根 结点的，和 不过根 结点的。

或者换种说法，LCA是全树的根结点的，或者不是根结点的。

（超喜欢这个字体 AwA ）

分类讨论绝对是树学界存在的最恶心的玩意。不会真的有人在代码里分类讨论吧，不会吧不会吧。

我想把这两种情况 归为一类 。

大眼观察法看出 Type\ 2 在以粉色点为根的时候就可以归纳为一种 Type\ 1 。

• A \bmod 3=1 , B \bmod 3=2
• A \bmod 3=2 , B \bmod 3=1

开三个桶来计数，tong_0,tong_1,tong_2分别存 \pmod 3=0,\pmod 3=1,\pmod 3=2 。

那么来个小加法原理就有了：

小心输出格式，甚至要约分。（淦

您吊打国集

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e4 + 7;
struct edge
{
    int to, next;
    int val;
} e[MAX << 1];
int head[MAX], eid = 0;
void adde(int x, int y, int w)
{
    e[++eid].to = y;
    e[eid].next = head[x];
    e[eid].val = w;
    head[x] = eid;
}
int N;
int size[MAX], son[MAX], SUM;
int vis[MAX];
int cent;
void getroot(int u, int lst)
{
    size[u] = 1;
    son[u] = 0;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        getroot(v, u);
        size[u] += size[v];
        son[u] = max(son[u], size[v]);
    }
    son[u] = max(son[u], SUM - son[u]);
    if (son[u] < son[cent])
    {
        cent = u;
    }
}
int ans;
int tong[3], dis[MAX];
void getdis(int u, int lst)
{
    tong[dis[u] % 3]++;//相应的桶++
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        dis[v] = dis[u] + e[i].val;
        getdis(v, u);
    }
}
int calc(int u, int w)
{
    dis[u] = w;
    tong[0] = tong[1] = tong[2] = 0;//先清空
    getdis(u, 0);
    return tong[1] * tong[2] * 2 + tong[0] * tong[0];
    //如上公式算得答案
}
void solve(int u)
{
    ans += calc(u, 0);
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to, w = e[i].val;
        if (vis[v])
        {
            continue;
        }
        ans -= calc(v, w);
        SUM = size[v];
        cent = 0;
        getroot(v, u);
        solve(cent);
    }
}
void output()
{
    int G = __gcd(ans, N * N);
    cout << ans / G << "/" << N * N / G << endl;
}
int main()
{
    cin >> N;
    for (int i = 1; i <= N - 1; i++)
    {
        int fr, to, val;
        cin >> fr >> to >> val;
        adde(fr, to, val);
        adde(to, fr, val);
    }
    SUM = N;
    son[0] = SUM;
    getroot(1, 0);
    solve(cent);
    output();
}

次次次模板题：[IOI2011]Race

刚爆踩完集训队，马上就IOI了（笑）

这题和纯模板题又有差别，在距离符合的情况下要求路径上边数最少。还是改 \operatorname{calc} 。

像这种多条件下求人上人的题目，多半是平衡树或堆。

因为要求的并非 全部路径 最优的一个，而是有条件限制（距离定为 K ）。

所以只能打平衡树了……

吗？

人生苦短，我用 set+lower\_bound 。遍历所有出现过的距离，查找的是能和它拼成 K 的长度中边数最少的。

因为题目大毒瘤，所以加了亿点卡常。

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define MP make_pair
#define SIT set<PII>::iterator
const int MAX = 2e5 + 7;
inline int Min(int x, int y)
{
    return x < y ? x : y;
}
inline int Max(int x, int y)
{
    return x > y ? x : y;
}
int read()
{
    int num = 0, bj = 0;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
        {
            bj = 1;
        }
        ch = getchar();
    }
    while (isdigit(ch))
    {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return bj ? -num : num;
}
struct edge
{
    int to, next;
    int val;
} e[MAX << 1];
int head[MAX], eid = 0;
inline void adde(int x, int y, int w)
{
    e[++eid].to = y;
    e[eid].next = head[x];
    e[eid].val = w;
    head[x] = eid;
}
int N, K, SUM;
int size[MAX], son[MAX];
int vis[MAX];
int cent;
inline void getroot(int u, int lst)
{
    size[u] = 1;
    son[u] = 0;
    for (register int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        getroot(v, u);
        size[u] += size[v];
        son[u] = Max(son[u], size[v]);
    }
    son[u] = Max(son[u], SUM - son[u]);
    if (son[u] < son[cent])
    {
        cent = u;
    }
}
set<PII> s;
int ans = 1e9 + 7;
PII apr[MAX];
int cntapr = 0;
int dis[MAX];
inline void getdis(int u, int lst, int path)
{
    if (path > ans || dis[u] > K)
    //到题解区学的剪枝，其实不难理解
    {
        return;
    }
    apr[++cntapr] = MP(dis[u], path);
    //装桶，第一维是长度，第二维是路径上的边数。
    for (register int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        dis[v] = dis[u] + e[i].val;
        getdis(v, u, path + 1);
    }
}
inline void calc(int u)
{
    s.clear();
    s.insert(MP(0, 0));
    for (register int i = head[u]; i; i = e[i].next)
    {

        int v = e[i].to, w = e[i].val;
        if (vis[v])
        {
            continue;
        }
        cntapr = 0;//清空
        dis[v] = w;
        getdis(v, u, 1);

        //现在 apr 数组里装得是v这棵子树上，各种新产生的路径
        for (int j = 1; j <= cntapr; j++)
        {
            int d = apr[j].first, p = apr[j].second;
            //取出距离和边数
            SIT pos = s.lower_bound(MP(K - d, 0));
            //查能拼的长度
            if (pos != s.end() && pos->first + d == K)
            {
                ans = Min(ans, pos->second + p);//反复取min
            }
        }
        //装进set
        for (int j = 1; j <= cntapr; j++)
        {
            s.insert(apr[j]);
        }
    }
}
inline void solve(int u)
{
    cent = 0;
    getroot(u, u);
    vis[cent] = 1;
    calc(cent);
    for (register int i = head[cent]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (vis[v])
        {
            continue;
        }
        SUM = size[v];
        solve(v);
    }
}
int main()
{
    cin >> N >> K;
    for (register int i = 1; i <= N - 1; i++)
    {
        int fr, to, val;
        fr = read(), to = read(), val = read();
        fr++;
        to++;//因为这题的申必编号从0开始，所以全体编号加1处理
        adde(fr, to, val);
        adde(to, fr, val);
    }
    cent = 0;
    SUM = son[0] = N;
    solve(1);
    if (ans == 1e9 + 7)
    {
        cout << -1 << "\n";
    }
    else
    {
        cout << ans << "\n";
    }
}

点分树（动态点分治）

“我真傻，真的，我以为三倍经验黑题躺在任务列表里就迟早会被切掉，谁知道等我切掉的时候已经掉紫了。”

处理什么问题：

带修树上点对距离查询。这里的“修”不会改变树的形态。

您会说：“我 O(1) 修改，每次查询都 O(n \log n) 跑一遍点分治不香吗？” 这是一种 O(q\cdot n\log n) 的优秀算(bao)法(li)。

抱歉，点分树可以达到 O(q\log n) 的效率。如果算上它上边套的别的数据结构（比如平衡树哇，堆哇），也一般能有 O(q\log^2 n) 的高性能。

思想是什么：

想想您的暴力为什么会有这么大的复杂度。

找重心，回答询问，修改，又找重心，又回答询问，又修改……

看得出，您的做法有不少重复的操作。

尝试优(tou)化(gong)算(jian)法(liao)。

询问和修改我们都不敢偷懒，只能从找重心开刀。

我们发现，因为树的形态始终不变，找到的重心永远都是那几个。

又想到，我们每一次统计答案（ \operatorname{calc} ），总是在递归重心时的 \operatorname{solve} 函数里。这是否表明一个重心点，它还能表示一些其他的有关答案的信息呢？

必然是可以的，我们甚至还能用取重心的搜索序建出一棵树来。这棵树就称作点分树。

接下来，我们声称：两个点在原树上的距离为他们的 真实距离 。（区别于点分树上的距离）

我这是一棵树（确信），树上有 6 个顶点。

我取重心 4 作为根，我开一个 tong\_4 装以 4 为根的子树中出现的 点到根的真实距离 情况。 （右边是当前 点分树 的形态）

我取重心 2 为根，距离情况再装桶。

如此往复。最终得到了图上的所有信息。

这些信息是可以在 O(n\log n) 时间内得到的。下面考虑修改：

如果我们要修改原树上 1\ 2 之间的边权，从 val=1 改为 val=2 。哪些桶里装的值会受影响？

大眼观察法， tong\_2 和 tong\_4 会受影响。

可见会受到修改的影响的，是这条边 在点分树上 的祖先们。

我们往下递归找重心时，记录一下每个重心是 从谁递归过来 的，记之为 fa 。（一般点分树的题不用建出真正的点分树形态，比如像这里只要记录其 点分树上 的父亲 fa 即可）。

向上跳 fa ，每跳到一个点，修改相应的数据结构。 （像这里就是修改桶里的值～）

我们珂以保证：这样跳 fa 可以只跳 \log n 次。

原因？

点分治拥有的 \log n 的优秀递归层数，使得点分树的层数也能控制在 \log n 。

而查询更是轻松，只需直接调用数据结构里的信息就可了。

妙到家。

劲爆习题：

模板题： QTREE5 - Query on a tree V

其实不是很板。/kk

修改：翻转颜色，查询：给定 u ，求树上距 u 最近白点。

一上来就整点“好康的”。可以充分感受点分树的恶意。(bushi

查询的是最值，那就不是开桶那么简单了。

我们要开堆。

每个点必然要开一个堆，装的是它的 点分树子树 里的点，到它的 真实距离 。（因为是最 小 值，所以开小根堆）

因为有时会有白点变成黑的，无法计入答案，所以要写一个 可删堆 AwA 。

这其实算得上一种小 trick ，下面有放代码的。

那么修改操作即为：

• 一个点 P 变白了 \rightarrow 跳到其 点分树上 的父亲 FA \rightarrow 往 FA 的堆里塞一个表示 P 到 FA\ 真实距离 的元素 \rightarrow 跳到更高一级的 FA \rightarrow 塞元素 \rightarrow\; \cdots

• 一个点 P 变黑了 \rightarrow 跳到其 点分树上 的父亲 FA \rightarrow 在 FA 的堆里删去表示 P 到 FA\ 真实距离 的元素 \rightarrow 跳到更高一级的 FA \rightarrow 删元素 \rightarrow\; \cdots

都维护了这么多东西了，那么查询操作就有 手 就 行。我们要查询一个点 P 的最近白点。

扫一遍它在 点分树 上的所有祖先。为什么是点分树？因为一个点的距离信息都保存在了它点分树上祖先的堆里，所以是在点分树上跳祖先。

取出祖先 FA 位置上堆的堆顶，这个堆顶就是所有过 FA 的 真实路径 中最短的一条。

这个堆顶和 P 到 FA 的 真实距离 可以拼起来，形成一个如树上路径 Case\ 1 的两点点距。

不断上跳 FA ，对点距多次取 min 。最终就能得到答案辣！

#include <bits/stdc++.h>
using namespace std;
#define RUN(u) for (int i = head[(u)]; i; i = e[i].next)
#define GI greater<int>
const int MAX = 1e5 + 7;
const int INF = 1e9 + 7;

/*存图组件*/
struct edge
{
    int next;
    int to;
} e[MAX << 1];
int head[MAX], eid = 0;
void adde(int x, int y)
{
    e[++eid].to = y;
    e[eid].next = head[x];
    head[x] = eid;
}

/*点分治组件*/
int size[MAX], son[MAX], vis[MAX];
int cent, N, Q, SUM;
void get_root(int u, int lst)
{
    size[u] = 1;
    son[u] = 0;
    RUN(u)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        get_root(v, u);
        size[u] += size[v];
        son[u] = max(son[u], size[v]);
    }
    son[u] = max(son[u], SUM - son[u]);
    if (son[u] < son[cent])
    {
        cent = u;
    }
}
int dis[27][MAX], dep[MAX];
//dis：表示某点到其fa的真实距离
//第二维是指该点的编号 第一维是指“这是它的第几级祖先” 

//dep：表示该点在点分树上的深度，这决定了它上面有几级祖先。
int fa[MAX];
void getdis(int u, int lst, int stp)
{
    dis[stp][u] = dis[stp][lst] + 1;
    RUN(u)
    {
        int v = e[i].to;
        if (vis[v] || v == lst)
        {
            continue;
        }
        getdis(v, u, stp);
    }
}

/*点分树组件*/
void solve(int u, int stp)//stp：遍历到的点分树深度
{

    /*点分治板子*/
    dep[u] = stp;
    vis[u] = 1;
    RUN(u)
    {
        int v = e[i].to;
        if (vis[v])
        {
            continue;
        }
        dis[stp][u] = 0;
        getdis(v, u, stp);
    }

    RUN(u)
    {
        int v = e[i].to;
        if (vis[v])
        {
            continue;
        }
        cent = 0;
        son[0] = INF;
        SUM = size[v];
        get_root(v, u);
        get_root(cent, u);
        fa[cent] = u;//一个点在点分树上的父亲即是它“从谁递归过来”
        solve(cent, stp + 1);
    }
}

priority_queue<int, vector<int>, GI> rema[MAX], dele[MAX];
//可删堆，现在还看不出什么高妙，详情见 query
//我们称rema为剩余堆，dele为删除堆

int color[MAX];//颜色
void update(int x)
{
    int u = x;
    for (int i = dep[x]; i; i--)
    {
        if (color[x] == 0)
        {
            rema[u].push(dis[i][x]);
            //若原为黑，则现在变为白，加点
        }
        else
        {
            dele[u].push(dis[i][x]);
             //若原为白，则现在变为黑，删点
        }
        u = fa[u];//跳fa
    }
    color[x] = 1 - color[x];
}

int query(int x)
{
    int u = x, ans = INF;
    for (int i = dep[x]; i; i--)
    {
        while (!rema[u].empty())
        {
            if (!dele[u].empty() && dele[u].top() == rema[u].top())
            //若一个元素同时出现在剩余堆和删除堆，则这是一个被删除过的元素。
            {
                dele[u].pop();
                rema[u].pop();
                //阴阳人滚出优先队列
            }
            else
            {
                ans = min(ans, dis[i][x] + rema[u].top());
                //反复取min
                break;
            }
        }
        u = fa[u];
    }
    if (ans == INF)
    {
        return -1;
    }
    return ans;
}
int main()
{
    cin >> N;
    for (int i = 1; i <= N - 1; i++)
    {
        int fr, to;
        cin >> fr >> to;
        adde(fr, to);
        adde(to, fr);
    }
    solve(1, 1);
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int opt;
        cin >> opt;
        if (opt == 0)
        {
            int num;
            cin >> num;
            update(num);
        }
        else
        {
            int num;
            cin >> num;
            cout << query(num) << endl;
        }
    }
}

冲高端题：[ZJOI2007]捉迷藏

是ZJOI远古题！

显然那时候浙江省选的毒瘤综合征就已经在潜伏期了。

相比上题，没有了确定的 u ，而是要在全树上查最大值。

上题要考虑的范围那么小，还仅仅卡着复杂度过题，这次有那么多条边要枚举。带毒瘤，爬了爬了。

想想有没有什么“高妙”做法。

全树最大值，所以我们需要开一个全局的大根堆，维护 点分树 上的最大 点对真实距离 。记此堆为 \mathtt{ALL} 。

上道题 “每个点开一个堆，装它的 点分树子树 里的点，到它的 真实距离 ” 的思路依然保留。记这些堆为 \mathtt{subtofa[1...n]}

但仅有一个 \mathtt{subtofa} 堆无法直接维护 \mathtt{ALL} 。我们可以再整一个堆用于过渡。

先更改 \mathtt{subtofa[1...n]} 的定义为：“每个点（称它为 u ）开一个堆，装 u 的 点分树子树 里的点，到 u 的父亲的真实距离 ”（差别在于真实距离是到它父亲的）。

再开一个堆表示 “对于一个点 u 在 点分树 中的每个儿子 v ，都把 \mathtt{subtofa[v]} 中最大的一个装进这个堆里”。记这种堆为 \mathtt{fainsub[1...n]} 。

代码中的这句话可以彰显出其关系：

fainsub[u].push(subtofa[cent].top());
        //存进subtofa的最大值

而关于 \mathtt{fainsub} 和 \mathtt{ALL} ，可以看出 \mathtt{ALL} 里装的东西始终为： 每个 \mathtt{fainsub} 中，堆顶的 两个长度的和 （参考以 Case\ 1 的形式拼接两个长度，以形成一条路径） 。

更新 \mathtt{ALL} 堆的代码实现～

void ins_ALL(int u)
{
    if (fainsub[u].size() >= 2)
    {
        ALL.push(fainsub[u].top() + fainsub[u].second());
        //ALL是自定义的“可删堆”类型，second取出的是其第二大的元素
    }
}

如果您对定义感到疑惑，这里给出一种感性理解（毕竟我也给这道题题解的各种定义看自闭过）：\texttt{subtofa} 维护的是纵向的距离最大值， \mathtt{fainsub} 维护的是横向的距离最大值。

给出一张图助于理解：

如果点 u 关灯，则将像上题一样，不断跳 fa ，将 \mathtt{subtofa[u].top()} 加入这个 fa 的 \mathtt{fainsub[fa]} ，再将新的 \mathtt{fainsub[fa]} 装进 \mathtt{ALL} 。

若开灯，则将以上操作改为删除元素。

自认为说的很详尽了。

#include <bits/stdc++.h>
using namespace std;
#define RUN(u) for (int i = head[(u)]; i; i = e[i].next)
#define GI greater<int>
const int MAX = 1e5 + 7;
const int INF = 1e9 + 7;

/*存边组件*/
struct edge
{
    int next;
    int to;
} e[MAX << 1];
int head[MAX], eid = 0;
int N, Q;
void adde(int x, int y)
{
    e[++eid].to = y;
    e[eid].next = head[x];
    head[x] = eid;
}

/*封装可删堆*/
struct removable_priority_queue
{
    priority_queue<int> rema, dele;
    void remove(int x)
    {
        dele.push(x);
    }
    void push(int x)
    {
        rema.push(x);
    }
    int top()
    {
        while (!rema.empty() && !dele.empty() && dele.top() == rema.top())
        {
            dele.pop();
            rema.pop();
        }
        return rema.top();
    }
    int second()
    {
        int maxx = top();
        rema.pop();
        int ans = top();
        rema.push(maxx);
        return ans;
    }
    int size()
    {
        return rema.size() - dele.size();
    }
} subtofa[MAX], fainsub[MAX], ALL;

/*用 fainsub 更新全局 ALL*/
void del_ALL(int u)
{
    if (fainsub[u].size() >= 2)
    {
        ALL.remove(fainsub[u].top() + fainsub[u].second());
    }
}
void ins_ALL(int u)
{
    if (fainsub[u].size() >= 2)
    {
        ALL.push(fainsub[u].top() + fainsub[u].second());
    }
}
/*点分治组件*/
int size[MAX], son[MAX];
int cent, SUM;
int vis[MAX];
void getroot(int u, int lst)
{
    size[u] = 1;
    son[u] = 0;
    RUN(u)
    {
        int v = e[i].to;
        if (v == lst || vis[v])
        {
            continue;
        }
        getroot(v, u);
        size[u] += size[v];
        son[u] = max(son[u], size[v]);
    }
    son[u] = max(son[u], SUM - son[u]);
    if (son[u] < son[cent])
    {
        cent = u;
    }
}

int dis[27][MAX];
int color[MAX];
void getdis(int u, int lst, int stp, int root)
{
    subtofa[root].push(stp);
    RUN(u)
    {
        int v = e[i].to;
        if (vis[v] || v == lst)
        {
            continue;
        }
        getdis(v, u, stp + 1, root);
    }
}

int fa[MAX];
void solve(int u)
{
    vis[u] = 1;
    RUN(u)
    {
        int v = e[i].to;
        if (vis[v])
        {
            continue;
        }
        cent = 0;
        son[0] = INF;
        SUM = size[v];
        getroot(v, u);
        fa[cent] = u;//记录fa
        getdis(v, u, 1, cent);
        fainsub[u].push(subtofa[cent].top());
        //存进subtofa的最大值
        solve(cent);
    }
    fainsub[u].push(0);//可以自己到自己
    ins_ALL(u);
}

/*LCA组件（蒟蒻太蔡了打了个倍增）*/
int dep[MAX], lg[MAX];
int father[MAX][27];
void LCA_prework(int u, int lst)
{
    dep[u] = dep[lst] + 1;
    father[u][0] = lst;
    for (int i = 1; i <= 17; i++)
    {
        father[u][i] = father[father[u][i - 1]][i - 1];
    }
    for (int i = head[u]; i; i = e[i].next)
    {
        if (e[i].to == lst)
        {
            continue;
        }
        LCA_prework(e[i].to, u);
    }
}
int LCA(int x, int y)
{
    if (dep[x] < dep[y])
    {
        swap(x, y);
    }
    while (dep[x] > dep[y])
    {
        x = father[x][lg[dep[x] - dep[y]] - 1];
    }
    if (x == y)
    {
        return x;
    }
    for (int i = lg[dep[x]] - 1; i >= 0; i--)
    {
        if (father[x][i] != father[y][i])
        {
            x = father[x][i];
            y = father[y][i];
        }
    }
    return father[x][0];
}
int dis_on_real(int x, int y)
{
    return dep[x] + dep[y] - dep[LCA(x, y)] * 2;
}

/*开灯*/
void turn_on(int u)
{
    del_ALL(u);
    fainsub[u].remove(0);//首先不能自己到自己了
    ins_ALL(u);
    for (int now = u; fa[now]; now = fa[now])//跳fa
    {
        int D = dis_on_real(u, fa[now]);
        del_ALL(fa[now]);//先取出第一层
        if (subtofa[now].size())
        {
            fainsub[fa[now]].remove(subtofa[now].top());
            //取出第二层
        }
        subtofa[now].remove(D);//铲除祸根
        if (subtofa[now].size())
        {
            fainsub[fa[now]].push(subtofa[now].top());//放回
        }
        ins_ALL(fa[now]);//放回
    }
}

/*关灯*/
void turn_off(int u)//见上
{
    del_ALL(u);
    fainsub[u].push(0);
    ins_ALL(u);
    for (int now = u; fa[now]; now = fa[now])
    {
        int D = dis_on_real(u, fa[now]);
        del_ALL(fa[now]);
        if (subtofa[now].size())
        {
            fainsub[fa[now]].remove(subtofa[now].top());
        }
        subtofa[now].push(D);
        if (subtofa[now].size())
        {
            fainsub[fa[now]].push(subtofa[now].top());
        }
        ins_ALL(fa[now]);
    }
}

/*多此一举的修改函数*/
void update(int u)
{
    if (color[u] == 0)
    {
        turn_on(u);
    }
    else
    {
        turn_off(u);
    }
}

int black;
int main()
{
    ios::sync_with_stdio(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        lg[i] = lg[i - 1] + (i == (1 << lg[i - 1]));
    }
    for (int i = 1; i <= N - 1; i++)
    {
        int fr, to;
        cin >> fr >> to;
        adde(fr, to);
        adde(to, fr);
    }
    LCA_prework(1, 0);
    SUM = N;
    cent = 0;
    son[0] = INF;
    getroot(1, 0);
    solve(cent);
    black = N;
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        char opt;
        cin >> opt;
        if (opt == 'G')
        {
            if (black == 0)
            {
                cout << -1 << "\n";
                continue;
            }
            if (black == 1)
            {
                cout << 0 << "\n";
                continue;
            }
            cout << ALL.top() << "\n";
        }
        else
        {
            int w;
            cin >> w;
            if (color[w] == 1)
            {
                black++;
            }
            else
            {
                black--;
            }
            update(w);
            color[w] = 1 - color[w];
        }
    }
}

有三倍经验 AwA ：Qtree4 （这题要小心带边权） QTREE4 - Query on a tree IV （我至今没卡完的常）

阴间题：[WC2014]紫荆花之恋

我 不 会（逃

以后来填坑。

无旋 treap

“这个splay就是逊啦！”

早就学过 splay ，但每次敲完都会出锅，总是要对着板子全文比较。

导致给了窝一个刻板印象：平衡树=不行。

平衡树什么时候时候才能站起来？气抖冷。

直到窝开始盘算着学无旋 treap 。

这是什么：

一种基于分裂合并操作的 treap ，可以跑持久化，但不能很轻松地维护 LCT 。

最重要的是，它很短。而且板子极为好背，针不戳。

思想是什么：

前置知识：知道普通 treap 的形态与性质。

考虑一棵 treap ，他在 val 的维度上维持二叉搜索树的性质，在 prio 维度上维持堆的性质。如下图：

即：

1. 其中序遍历为原序列的 按 val 的有序排列（二叉搜索树的性质）

2. 对于任何一棵子树，都满足 根的 prio 值大于儿子的 prio （堆的性质）

无旋 treap 的特性：

（接下来的叙述将会围绕着如何使无旋 treap 完成 ”加点、删点、查第 k 大、查排名、查前驱后继“ 来展开！）

人群当中突然钻出来一个奆佬，表示发现了一个二叉搜索树的巧妙性质：

以任意一个 在值域当中的数 val 为分割线，一定能将二叉搜索树分成 “小于等于 val” 与 “大于 val” 两部分，且这两部分分开来看也各是一棵二叉搜索树。

还是以原来这棵树为例，如果我们从 val=5 切割：

（更正：右半边 val=1 的结点对应标号应为 4 ）

我们发现这一个数就把他分（ \operatorname{split} ）成了两棵二叉搜索树。

我们借助这一性质，来尝试进行一些操作。

加点：

首先考虑，我们直接加点时，往往只能做到把新点挂在外围。然后再经过胡乱操作（ 如 splay 中的 \operatorname{rotate} ）保送这个新点到该去的位置。

而无旋 treap 则没有这样的烦恼。

倘若我们要加一个 val=2 的点，我们先把原树按 2 \operatorname{split} 出了 L,R 两棵子树。

这时，我们创造一个游离的结点，保存新元素的值。

如此实现：

struct node
{
    int son[2];//左右儿子
    int val;//val值
    int prio;//随机赋给其的prio值，用于建出一个堆
    int size;//以之为根的子树大小
} T[MAX];

#define ls(a) T[(a)].son[0]
#define rs(a) T[(a)].son[1]//宏定义

int ROOT, cnt =  0;//根、当前点的编号

void add(int x)//造一个游离点
{
    T[++cnt].size = 1;
    T[cnt].val = x;
    T[cnt].prio = rand();
    ls(cnt) = rs(cnt) = 0;//各种初始化
}

此时，我们发现原来的平衡树，它裂了（悲），但问题不大，我们可以想办法合并（ \operatorname{merge} ）。

因为我们合并以后，需要仍然保持 treap 的性质。故应判断需要合并的两棵树的 树根的 prio 值的大小关系 。谁的 prio 的更小，谁就挂在对方的下面。（怪）

这样我们先将这个游离点与左树 \operatorname{merge} ，再将左树与右树 \operatorname{merge} 即可～

（图被我弄丢了ToT ，或许可以使用上面那张图格物致知？）

那么，当我们在加点过程中，把一个不平衡的二叉搜索树 裂开来 ，再以一种平衡的方式 合并 回去，就能起到“制衡”的作用辣！AwA

该部分代码如下：

void push_up(int p)//更新size
{
    T[p].size = T[ls(p)].size + T[rs(p)].size + 1;
}
void split(int p, int x, int &L, int &R)
//p,x:当前递归到的点、需要加的值
//&L,&R:传进来两个地址来把最后分出的L,R树的根结点编号运出去
{
    if (!p)//递归边界
    {
        L = 0;
        R = 0;
        return;
    }
    if (T[p].val <= x)//判断条件，分裂（背板即可）
    {
        L = p;
        split(rs(p), x, rs(p), R);
    }
    else
    {
        R = p;
        split(ls(p), x, L, ls(p));
    }
    push_up(p);
}
int merge(int Lroot, int Rroot)//合并的左右树根
{
    if (!Lroot)
    {
        return Rroot;
    }
    if (!Rroot)
    {
        return Lroot;
    }//倘若另一边为空，则不用和空气贴贴了，直接返回

    if (T[Lroot].prio < T[Rroot].prio)//否则判断谁在下面
    {
        rs(Lroot) = merge(rs(Lroot), Rroot);
        //返回的值是两树合并后的大树的树根
        push_up(Lroot);
        return Lroot;
    }
    else
    {
        ls(Rroot) = merge(Lroot, ls(Rroot));
        push_up(Rroot);
        return Rroot;
    }
}
void insert(int x)
{
    int l, r;
    split(ROOT, x, l, r);//先裂开来
    add(x);//创造游离点
    ROOT = merge(merge(l, cnt), r);
    //先合并左树和新点，再合并左树和右树
}

删点：

不会真的有人删点是去把目标结点清空的吧，不会吧不会吧。