脚本宝典收集整理的这篇文章主要介绍了Dash Speed，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

1 Dash SPEed

• 题目链接：http://bzoj.org/d/dxlc2021/p/P000018

2 题目描述

时间限制 (1000ms) | 空间限制 (128M)

比特山是比特镇的飙车圣地。在比特山上一共有 (n) 个广场，编号依次为 (1) 到 (n)，这些广场之间通过 (n−1) 条双向车道直接或间接地连接在一起，形成了一棵树的结构。

因为每条车道的修建时间以及建筑材料都不尽相同，所以可以用两个数字 (l_i,r_i) 量化地表示一条车道的承受区间，只有当汽车以不小于 (l_i) 且不大于 (r_i) 的速度经过这条车道时，才不会对路面造成伤害。

(Byteasar) 最近新买了一辆跑车，他想在比特山飙一次车。(Byteasar) 计划选择两个不同的点 (S,T)，然后在它们树上的最短路径上行驶，且不对上面任意一条车道造成伤害。

(Byteasar) 不喜欢改变速度，所以他会告诉你他的车速。为了挑选出最合适的车速，(Byteasar) 一共会向你询问 (m) 次。请帮助他找到一条合法的道路，使得路径上经过的车道数尽可能多。

数据范围： 对于 (100%) 的数据，(1le u_i, v_i,q_i le n, 1le l_ile r_ile n) 。

3 题解

这道题需要用到线段树分治这个小技巧。

在讲线段树分治之前，我们需要先了解可撤销并查集。

可撤销并查集，顾名思义，就是可以将操作撤销的并查集。注意这里说的是撤销而不是可持久化，意味着它只能按照操作的顺序倒序把操作撤销，而不能直接删除某一操作。

具体地，我们可以用一个栈来记录每一步中我们合并的两个集合，然后每次撤销时将栈顶弹出，并将两个集合分开，把父亲赋为自己即可。

容易发现，速度的范围是 (1) 到 (n)，所以我们可以将所有询问的答案先预处理出来，然后一起回答。我们发现，此时一个速度只会出现一次，因此将速度看作时刻，将每一条边的速度限制看作这条边的出现时间区间，问题就变成了：每条边有一个出现和消失的时间，在任意时刻查询图中所有连通块的最长链的最大值。

我们发现：对于一个时刻来说，所有的区间包括当前点的边都出现在图上，这启发我们用一些数据结构来维护这个信息。于是我们考虑线段树。

但这里是加边操作，而不是单纯的加减，所以我们必须要遍历到叶子结点才能回答询问。容易发现，如果我们要遍历到叶子结点，那么整个过程就类似于一个 (DFs)。因此，我们需要一个能够支持动态加边和撤销操作并可以快速回答所有连通块中最长链长度的最大值的数据结构——可撤销并查集。

此时，大概的思路就明确了：我们按照速度建线段树，然后对于每一个区间记一个 (vector) 用来存储哪些边出现的速度完全包含当前速度区间。当我们遍历到当前区间时，我们就可以用可撤销并查集把所有边所连的点所在集合合并在一起。

现在我们唯一的问题就在于怎么用并查集求出所有连通块中最长链的长度的最大值。

性质：设 (A) 树的直径两端点是 (u_1, v_1)，(B) 树的直径两端点是 (u_2, v_2)，那么在用任意一条边连接 (A) 树与 (B) 树后，新的树的直径一定是由 (u_1, v_1, u_2, v_2) 四个点组成的。

为了证明这个性质，我们先证明一个引理：树上任意一点出发到达的点中的最远点之一一定是直径端点。

证明：

反证法。

假设我们从 (x) 出发，抵达的最远点是 (y)，树的直径是 (u) 和 (v)。

那么我们当前路径和树的直径有两种情况，一种是不相交，一种是相交。

因为树连通，所以不相交时一定存在一条路径连接路径 (x to y) 和路径 (u to v)。我们称它为 (p to q)（假设 (p) 为 (xto y) 上一点，(q) 为 (u to v) 上一点）。将任意两点 (a, b) 间距离记作 (dist_{a, b})。

当 (p) 不与 (x, y) 重合，(q) 不与 (u,v) 重合时，容易发现：因为 (xto y) 是从 (x) 出发的最长链，所以有 (dist_{p, y} ge dist_{p, q} + dist_{q, v})。因为 (u to v) 是直径，所以一定是从 (u) 出发的最长链，也就说明 (dist_{p, q} + dist_{p, y} le dist_{q, v})

将两式联立，得 (dist_{p, q} le 0)，与题设不符，故矛盾。

当 (p) 点与 (x) 点重合时容易发现对上式没有影响，而 (p) 点与 (y) 点重合时 (x to y) 一定不是从 (x) 出发的最长链。当 (q) 点与 (u) 点重合时，(x to y) 一定不是从 (x) 出发的最长链，因为直径是最长的。而当 (q) 点与 (v) 点重合时，(u to v) 就不是直径了，故矛盾。

当两条路径相交时，那么设第一个交点为 (p)，容易发现：从 (p) 到 (y) 的距离一定大于等于从 (p) 到 (v) 的距离，否则最远点就是 (v)，而 (p) 到 (v) 的距离一定大于等于从 (p) 到 (y) 的距离，否则 (u to v) 就不是直径，故矛盾。

引理得证。

性质证明：

如果新树的直径不是原来两个直径之一，那么新树的直径一定经过新加的边。设新加的边连接点 (s) 和点 (b)（点 (s) 在 (A) 树中，点 (b) 在 (B) 树中），那么直径在 (A) 树的一端 (p) 到 (s) 一定是直径的一部分。此时这一部分跟剩下的一部分明显没有关系，而根据引理，从 (s) 出发的最长链一定是 (u, v) 之一。(B) 树那一端同理。

性质得证。

因此，我们只需要对于每个集合记下直径端点，然后合并时稍微分类讨论一下即可。这里需要一个倍增求出树上两点距离。

@R_392_1304@为 (O(n LOG_2^2n))。

然后发现不太行，需要卡常。

然后我们发现 (dist) 调用了很多遍，很浪费时间。于是我们把 (lca) 改成用欧拉序加 (st) 表 (O(1)) 查询，就过掉了，跑的飞快而且不用卡常。

4 代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorIThm>
#include <queue>
#include <;map>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
const int N = 3e5 + 10;
#define pii pair<int,int>
#define mp make_pair
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int n, m, u, v, tot, logt, Q, cnt;
int head[N], ver[N * 2], last[N * 2], ans[N], st[N * 2][30], dep[N];
int fa[N], siz[N], one[N], two[N], euler[N * 2], L[N], id[N];
stack<pair<pair<pii, pii>,pii> > s;
void add(int x, int y)
{
    ver[++tot] = y;
    last[tot] = head[x];
    head[x] = tot;
}
void dfs(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    euler[++cnt] = x;
    id[x] = cnt;
    for (int i = head[x]; i; i = last[i])
    {
        int y = ver[i];
        if (y == fa) continue;
        dfs(y, x);
        euler[++cnt] = x;
    }
}
void init()
{
    for (int i = 1; i <= cnt; i++) st[i][0] = euler[i];
    for (int i = 1; i <= logt; i++)
    {
        for (int j = 1; j <= cnt - (1 << i) + 1; j++)
        {
            if (dep[st[j][i - 1]] < dep[st[j + (1 << (i - 1))][i - 1]]) st[j][i] = st[j][i - 1];
            else st[j][i] = st[j + (1 << (i - 1))][i - 1];
        }
    }
}
int lca(int l, int r)
{
    l = id[l], r = id[r];
    if (l > r) swap(l, r);
    logt = L[r - l + 1];
    if (dep[st[l][logt]] < dep[st[r - (1 << logt) + 1][logt]]) return st[l][logt];
    return st[r - (1 << logt) + 1][logt];
}
int dist(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];}
int find(int x)
{
    if (fa[x] == x) return x;
    return find(fa[x]);
}
void merge(int &amp;x, int &y)
{
    if (x == y)
    {
        s.push(mp(mp(mp(-1, -1), mp(-1, -1)), mp(-1, -1)));
        return ;
    }
    if (siz[x] > siz[y]) swap(x, y); // x -> y
    s.push(mp(mp(mp(one[x], two[x]), mp(one[y], two[y])), mp(x, y)));
    fa[x] = y;
    siz[y] += siz[x];
    int maxn = max(dist(one[x], two[x]), dist(one[y], two[y]));
    maxn = max(maxn, max(dist(one[x], one[y]), dist(one[x], two[y])));
    maxn = max(maxn, max(dist(two[x], one[y]), dist(two[x], two[y])));
    if (dist(one[x], two[x]) == maxn)
    {
        one[y] = one[x];
        two[y] = two[x];
        return ;
    }
    if (dist(one[y], two[y]) == maxn) return ;
    if (dist(one[x], one[y]) == maxn)
    {
        two[y] = one[y];
        one[y] = one[x];
        return ;
    }
    if (dist(one[x], two[y]) == maxn)
    {
        one[y] = one[x];
        return ;
    }
    if (dist(two[x], one[y]) == maxn)
    {
        two[y] = one[y];
        one[y] = two[x];
        return ;
    }
    if (dist(two[x], two[y]) == maxn)
    {
        one[y] = two[x];
        return ;
    }
}
void back()
{
    pair<pair<pii, pii>,pii> x;
    x = s.top();
    s.pop();
    if (x.First.first.first == -1) return ;
    fa[x.second.first] = x.second.first;
    one[x.second.second] = x.first.second.first;
    two[x.second.second] = x.first.second.second;
    one[x.second.first] = x.first.first.first;
    two[x.second.first] = x.first.first.second;
    siz[x.second.second] -= siz[x.second.first];
}
struct node
{
    int l, r;
    vector<int> v;
}t[N * 4];
void build(int p, int l, int r)
{
    t[p].l = l;
    t[p].r = r;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r); 
}
void insert(int p, int l, int r, int d)
{
    if (t[p].l >= l && t[p].r <= r)
    {
        t[p].v.push_back(d);
        return ;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) insert(p * 2, l, r, d);
    if (r > mid) insert(p * 2 + 1, l, r, d);
}
void query(int p, int maxn)
{
    for (int i = 0; i < t[p].v.size(); i++)
    {
        int x = ver[t[p].v[i]], y = ver[t[p].v[i] ^ 1];
        int fx = find(x), fy = find(y);
        merge(fx, fy);
        maxn = max(maxn, dist(one[fy], two[fy]));
    }
    if (t[p].l == t[p].r)
    {
        ans[t[p].l] = maxn;
        for (int i = 0; i < t[p].v.size(); i++) back();
        return ;
    }
    query(p * 2, maxn);
    query(p * 2 + 1, maxn);
    for (int i = 0; i < t[p].v.size(); i++) back();
}
int main()
{
    freopen("ds.in", "r", stdin);
    freopen("ds.out", "w", stdout);
    int l, r;
    tot = 1;
    n = read(), m = read();
    for (int i = 2; i <= n * 2; i++) L[i] = L[i / 2] + 1;
    logt = L[n * 2];
    for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1, one[i] = two[i] = i;
    build(1, 1, n);
    for (int i = 1; i < n; i++)
    {
        u = read(), v = read(), l = read(), r = read();
        add(u, v);
        add(v, u);
        insert(1, l, r, tot);
    }
    dfs(1, 0);
    init();
    query(1, 0);
    for (int i = 1; i <= m; i++)
    {
        Q = read();
        PRintf("%dn", ans[Q]);
    }
    return 0;
}

欢迎关注

脚本宝典总结

以上是脚本宝典为你收集整理的Dash Speed全部内容，希望文章能够帮你解决Dash Speed所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。