[Luogu]P4374 [USACO18OPEN]Disruption P
本文最后更新于 95 天前,其中的信息可能已经有所发展或是发生改变。

上区间取 min 转化为树上区间染色的神奇思路。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp4374/

解法

不难发现,额外的双向道路的两个端点,在树上的简单路径上的边,被割断后,都可以走这条双向道路。
一个很自然的想法就是使用轻重链剖分线段树,维护区间最小值,进行区间取 min 更新,复杂度 $O(n \log ^2 n)$.
但可以通过对双向道路的边权进行排序,转化为染色问题。
具体地,将双向道路以权值从大到小排序,转化为区间染色,每次染色都能覆盖上次的颜色,那么这个问题就相当经典了。
同样可以使用线段树区间覆盖来维护染色,但复杂度依然是 $O(n \log ^2 n)$ 的。
然而,染色问题有着更优的解决方法。有的人称为并查集,或者双向链表、缩点等等。

染色例题

核心思想:逆序处理,将覆盖转化为跳过。由于染色的区间连续,因此可以在遇到一段已染色区间时,跳过该段区间,使每个点都只会被染色一次。
感性理解时间复杂度是 $O(n)$ 的,这里不深入研究了。


Update on 10/21/2020:
经过一定的思考,发现我原先的代码复杂度应该是假的。
原先的写法相当于不进行路径压缩的并查集,因为每个点虽然只需要染色一次,但会重复跳到已被染色的点上。具体地,从深向浅染色一条链,每次要求从链顶到链底染色,每次需要从链底跳到链顶,而由于没有路径压缩,相当于暴力跳点,会退化到 $O(n^2)$.
因此需要对这个并查集进行路径压缩优化。而由于不使用按秩合并,最坏复杂度是 $O(\log n)$ 的。

这里放一下原先的代码。
Old Version


在本题中,同样可以使用这个办法来进行染色。
双向道路按权值从小到大排序。
将简单路径拆成 $\texttt{u} \to \texttt{lca}$ 与 $\texttt{v} \to \texttt{lca}$ 两条,分别进行染色即可。
并查集维护某个点的祖先中,第一个未被染色的点。
将边转化为点后,注意 $\texttt{lca}$ 节点代表其通向父亲的边,是不用染色的。

代码

实现中,使用了轻重链剖分求 $\texttt{lca}$,时间复杂度 $O(n\log n)$.

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
const int maxn = 5e4 + 100;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc()) ;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}

struct node
{
    int to, next,id;
} E[maxn << 1];
int head[maxn], tot;
inline void add(int x, int y, int id) { E[++tot].next = head[x], E[tot].to = y, E[tot].id = id, head[x] = tot; }
struct edge
{
    int u, v, w;
} G[maxn];
bool cmp(const edge& a, const edge& b) { return a.w < b.w; }

//you can skip this part
int dep[maxn], size[maxn], son[maxn], top[maxn], fa[maxn], id[maxn], ANS[maxn];
void dfs1(int u)
{
    size[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        id[v] = E[p].id, fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), size[u] += size[v];
        if (size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u)
{
    if(!son[u]) return;
    top[son[u]] = top[u], dfs2(son[u]);
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa[u] || v == son[u]) continue;
        top[v] = v, dfs2(v);
    }
}
int lca(int x, int y)
{
    for (; top[x] != top[y]; x = fa[top[x]]) if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
    return dep[x] < dep[y] ? x : y;
}
//region end

int bel[maxn], up[maxn];
int find(int x) { return x == up[x] ? x : up[x] = find(up[x]); }
void update(int x, int y, int c)  //y is the ancestor of x
{
    //update from x to y (excluding y) with color c
    for (x = find(x); dep[x] > dep[y]; x = find(x)) bel[x] = c, up[x] = fa[x];
    //only set up[x] to fa[x], then leave it to path compression
}
int n, m;
int main()
{
    read(n), read(m);
    for (int i = 1, a, b; i < n; ++i) read(a), read(b), add(a, b, i), add(b, a, i);
    dep[1] = 1, dfs1(1), top[1] = 1, dfs2(1);
    for (int i = 1; i <= m; ++i) read(G[i].u), read(G[i].v), read(G[i].w);
    std::sort(G + 1, G + 1 + m, cmp);
    for (int i = 1; i <= n; ++i) up[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int l = lca(G[i].u, G[i].v);
        update(G[i].u, l, i), update(G[i].v, l, i);
    }
    for (int i = 2; i <= n; ++i) ANS[id[i]] = bel[i] ? G[bel[i]].w : -1;
    for (int i = 1; i < n; ++i) printf("%d\n", ANS[i]);
    return 0;
}
本文标题:[Luogu]P4374 [USACO18OPEN]Disruption P
本文作者:Clouder
本文链接: https://www.codein.icu/lp4374/
转载请标明。

评论

  1. 3月前
    2020-10-22 1:54:59

    您又发表您的不刊之论了

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇