P3979 遥远的国度:换根树剖

遥远的国度

题目描述

zcwwzdjn 在追杀 zhx ,而 zhx 逃入了一个遥远的国度。当 zcwwzdjn 准备进入遥远的国度继续追杀时,守护神 RapiD 阻拦了 zcwwzdjn 的去路,他需要 zcwwzdjn 完成任务后才能进入遥远的国度继续追杀。

问题是这样的:遥远的国度有 n 个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,第 i 个的防御值为 val_i,有些时候 RapiD 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。

RapiD 想知道在某个时候,如果把首都看做整棵树的根的话,那么以某个城市为根的子树的所有城市的防御值最小是多少。

由于 RapiD 无法解决这个问题,所以他拦住了 zcwwzdjn 希望他能帮忙。但 zcwwzdjn 还要追杀 zhx,所以这个重大的问题就被转交到了你的手上。

输入格式

1 行两个整数 n\ m,代表城市个数和操作数。

2 行至第 n 行,每行两个整数 u\ v,代表城市 u 和城市 v 之间有一条路。

n+1 行,有 n 个整数,第 i 个代表第 i 个点的初始防御值 val_i

n+2 行一个整数 id,代表初始的首都为 id

n+3 行至第 n+m+2 行,首先有一个整数 opt

如果 opt=1,接下来有一个整数 id,代表把首都修改为 id

如果 opt=2,接下来有三个整数 x\ y\ v,代表将 x\ y 路径上的所有城市的防御值修改为 v

如果 opt=3,接下来有一个整数 id,代表询问以城市 id 为根的子树中的最小防御值。

输出格式

对于每个 opt=3 的操作,输出一行代表对应子树的最小点权值。

样例 #1

样例输入 #1

3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1

样例输出 #1

1
2
3
4

提示

对于 20\% 的数据,n\le 1000,m\le 1000

对于另外 10\% 的数据,n\le 100000,m\le 100000,保证修改为单点修改。

对于另外 10\% 的数据,n\le100000,m \le 100000,保证树为一条链。

对于另外 10\% 的数据,n\le 100000,m\le100000,没有修改首都的操作。

对于 100\% 的数据,1 \leq n\le 100000,1 \leq m \le 100000,0<val_i<2^{31}

  • Code

    #include <bits/stdc++.h>
    #define ls (x << 1)
    #define rs (ls | 1)
    #define mids(l, r) const int mid = l + r >> 1
    #define v0 void(0)
    using namespace std;
    using cint = const int&;
    using ll = long long;
    using cll = const ll&;
    constexpr int maxn = 100001, lim = 20;
    constexpr ll inf = 0x3f3f3f3f3f3f3f;
    
    char opt;
    int n, m, u, v, rt, x, y, k, cnt, dfns, top[maxn], dfn[maxn], dep[maxn], lg[maxn], f[lim + 1][maxn], head[maxn], siz[maxn], son[maxn];
    ll a[maxn], val[maxn], seg[maxn << 2], tag[maxn << 2];
    
    struct { int nxt, v; }edge[maxn << 1];
    inline void addedge(cint u, cint v) {
        edge[++cnt] = { head[u], v };
        head[u] = cnt;
    }
    inline void dfs1(cint u, cint fa) {
        int maxsiz = 0;
        dep[u] = dep[f[0][u] = fa] + (siz[u] = 1);
        for (int i = 1; f[i - 1][u]; ++i)
            f[i][u] = f[i - 1][f[i - 1][u]];
        for (auto i = head[u]; i; i = edge[i].nxt) {
            const auto v = edge[i].v;
            if (v == fa) continue;
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > maxsiz)
                maxsiz = siz[son[u] = v];
        }
    }
    inline void dfs2(cint u, cint tp) {
        top[u] = tp;
        a[dfn[u] = ++dfns] = val[u];
        if (!son[u])
            return;
        dfs2(son[u], tp);
        for (auto i = head[u]; i; i = edge[i].nxt) {
            const auto v = edge[i].v;
            if (v == f[0][u] || v == son[u]) continue;
            dfs2(v, v);
        }
    }
    inline void pushdown(cint x) {
        if (tag[x]) seg[rs] = tag[rs] = seg[ls] = tag[ls] = tag[x];
    }
    inline void pushup(cint x) {
        if (tag[ls] == tag[rs]) tag[x] = tag[ls];
        else tag[x] = 0;
        seg[x] = min(seg[ls], seg[rs]);
    }
    void build(cint x, cint l, cint r) {
        if (l == r) return tag[x] = seg[x] = a[l], v0;
        mids(l, r);
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(x);
    }
    inline void setto(cint x, cll v) { seg[x] = tag[x] = v; }
    void allset(cint x, cint ml, cint mr, cint ql, cint qr, cll v) {
        if (ql <= ml && mr <= qr) return setto(x, v);
        pushdown(x);
        mids(ml, mr);
        if (mid >= ql) allset(ls, ml, mid, ql, qr, v);
        if (mid < qr) allset(rs, mid + 1, mr, ql, qr, v);
        pushup(x);
    }
    ll get(cint x, cint ml, cint mr, cint ql, cint qr) {
        if (ql <= ml && mr <= qr) return seg[x];
        pushdown(x);
        mids(ml, mr);
        ll ans = inf;
        if (mid >= ql) ans = min(ans, get(ls, ml, mid, ql, qr));
        if (mid < qr) ans = min(ans, get(rs, mid + 1, mr, ql, qr));
        return ans;
    }
    inline void add(int u, int v, cll k) {
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            allset(1, 1, n, dfn[top[u]], dfn[u], k);
            u = f[0][top[u]];
        }
        if (dep[u] < dep[v]) swap(u, v);
        allset(1, 1, n, dfn[v], dfn[u], k);
    }
    inline int getfa(int u, int k) {
        while (k) {
            u = f[lg[k]][u];
            k ^= (1 << lg[k]);
        }
        return u;
    }
    signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n >> m;
        for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i < n; ++i) {
            cin >> v >> u;
            addedge(v, u);
            addedge(u, v);
        }
        for (int i = 1; i <= n; ++i) cin >> val[i];
        dfs1(1, 0);
        dfs2(1, 1);
        cin >> rt;
        build(1, 1, n);
        while (m--)
            switch (cin >> opt; opt) {
            case '1':
                cin >> rt;
                break;
            case '2':
                cin >> x >> y >> k;
                add(x, y, k);
                break;
            default:
                cin >> x;
                if (x == rt) cout << seg[1] << '\n';
                else if (dep[x] < dep[rt] && f[0][y = getfa(rt, dep[rt] - dep[x] - 1)] == x) {
                    ll a = get(1, 1, n, 1, dfn[y] - 1);
                    if (dfn[y] + siz[y] <= n)
                        a = min(a, get(1, 1, n, dfn[y] + siz[y], n));
                    cout << a << '\n';
                }
                else
                    cout << get(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n';
                break;
            }
    }
    

    注意数据范围

    P3979 遥远的国度
    719ms /  23.47MB /  3.46KB C++20
    
  • Tip

显然,根据rt与x的位置关系,若rt在x子树(1=root)内,新x子树(rt=root)包含除rt方向之外一切

暂无评论

发送评论 编辑评论


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