首页 > 其他分享 >P3979 遥远的国度 题解

P3979 遥远的国度 题解

时间:2023-07-29 17:55:37浏览次数:42  
标签:hson int 题解 top tr dep 国度 P3979 id

P3979 遥远的国度

题意

一棵树,\(n\le 10^5\),三个操作,\(m\le 10^5\),点带权。

  1. 换根
  2. 路径推平
  3. 子树查最小值

思路

如果没有换根,操作 2, 3 是裸的树剖,考虑换根后的询问如何处理。

显然不能再做一遍树剖,只能假装我们换根了,询问可以分成四种情况,令原根为 \(root\),新根为 \(id\),查询点为 \(x\):

  1. \(x = id\),全局最小值;
  2. \(x\) 在 \(id\) 的子树内,原子树最小值
  3. \(x\) 在 \(root\) 到 \(id\) 的路径上,即 \(id\) 在 \(x\) 的原子树内,则询问等价于除了以 \(id\) 所在的 \(x\) 的子树中所有点的查询。
  4. \(x\) 和 \(id\) 不在同一颗 \(root\) 的子树内, 原子树最小值。

最棘手的是情况 3,如果 \(\min\) 的贡献可以消除,只需要用全局贡献减去子树贡献,然而 \(\min\) 操作的属性并不支持贡献的消除,所以只能反向考虑问题,由于子树内的点的编号是连续的,所以可以考虑合并左半部分的贡献与右半部分的贡献。

如果 \(LCA(x, id) = x\),则 \(id\) 在 \(x\) 的子树内

// Problem: P3979 遥远的国度
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-07-29 13:47:25

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define inf (int)2e18
using namespace std;
const int N = 1e5 + 10;

int n, m, temp[N];
vector<int> g[N];

int sz[N], hson[N], dfn[N], id[N], top[N], fa[N], w[N], tmst, dep[N];
void dfs1(int u, int fat)
{
    fa[u] = fat, sz[u] = 1, dep[u] = dep[fat] + 1;
    for(auto v : g[u])
    {
        if(v == fa[u]) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[hson[u]])
            hson[u] = v;
    }
}

void dfs2(int u, int anc)
{
    dfn[++ tmst] = u, id[u] = tmst, w[tmst] = temp[u], top[u] = anc; 
    if(!hson[u]) return ;
    dfs2(hson[u], anc);
    for(auto v : g[u])
    {
        if(v == fa[u] || v == hson[u]) continue;
        dfs2(v, v);
    }
}

// The code below implemented a Segment Tree

struct qwq
{
    int l, r, dat, tag;
} tr[N << 2];

void up(int u)
{
    tr[u].dat = min(tr[u << 1].dat, tr[u << 1 | 1].dat);
}

void down(int u)
{
    if(tr[u].tag == 0) return ;
    tr[u << 1].dat = tr[u << 1 | 1].dat = tr[u].tag;
    tr[u << 1].tag = tr[u << 1 | 1].tag = tr[u].tag;
    tr[u].tag = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, inf, 0};
    if(l == r) tr[u].dat = w[l], tr[u].tag = w[l]; // TODO
    else build(u << 1, l, l + r >> 1), build(u << 1 | 1, (l + r >> 1) + 1, r), up(u);
}

void update(int u, int ql, int qr, int v)
{
    int l = tr[u].l, r = tr[u].r, mid = l + r >> 1;
    if (ql <= l && qr >= r)
    {
        tr[u].dat = v, tr[u].tag = v;
        return;
    }
    down(u);
    if (ql <= mid) update(u << 1, ql, qr, v);
    if (qr > mid)  update(u << 1 | 1, ql, qr, v);
    up(u);
}

int query(int u, int ql, int qr)
{
    int l = tr[u].l, r = tr[u].r, mid = l + r >> 1;
    if (ql <= l && qr >= r)
        return tr[u].dat;
    down(u);
    int tmp = inf;
    if (ql <= mid) tmp = query(u << 1, ql, qr);
    if (qr > mid)  tmp = min(tmp, query(u << 1 | 1, ql, qr));
    up(u);
    return tmp;
}

int LCA(int a, int b)
{
    while(top[a] != top[b])
    {
        if(dep[top[a]] < dep[top[b]]) b = fa[top[b]];
        else a = fa[top[a]];
    }
    return (dep[a] < dep[b] ? a : b);
}

void HLDupdate(int a, int b, int v)
{
    while(top[a] != top[b])
    {
        if(dep[top[a]] < dep[top[b]]) swap(a, b);
        update(1, id[top[a]], id[a], v);
        a = fa[top[a]];
    }
    if(dep[top[a]] > dep[top[b]]) swap(a, b);
    update(1, id[a], id[b], v);
}

int jump(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        if(fa[top[x]] == y) return top[x];
        x = fa[top[x]];
    }
    return (dep[x] < dep[y] ? hson[x] : hson[y]);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for(int i = 1, a, b; i < n; i ++)
        a = read(), b = read(), g[a].push_back(b), g[b].push_back(a);
    for(int i = 1; i <= n; i ++)
        temp[i] = read();
    dfs1(1, 1), dfs2(1, 1);
    build(1, 1, n);
    int root = read();
    while(m --)
    {
        int op, a, b, c;
        op = read();
        if(op == 1)
            root = read();
        else if(op == 2)
        {
            a = read(), b = read(), c = read();
            HLDupdate(a, b, c);
        }
        else
        {
            int x = read();
            if(root == x)
                cout << query(1, 1, n) << '\n';
            else
            {
                int y = jump(root, x);
                if(LCA(x, root) == x)
                    cout << min(query(1, 1, id[y] - 1), (id[y] + sz[y] <= n ? query(1, id[y] + sz[y], n) : inf)) << '\n';
                else 
                    cout << query(1, id[x], id[x] + sz[x] - 1) << '\n';
            }
        }
    }

    return 0;
}

标签:hson,int,题解,top,tr,dep,国度,P3979,id
From: https://www.cnblogs.com/MoyouSayuki/p/17590205.html

相关文章

  • luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
    目录题目大意解题思路code题目大意题目链接给出一张\(n\)个点\(m\)条边的连通无向图,边带边权\(w_i\)。有以下三种操作,共\(q\)次:\(\centerdot\)在点\(x,y\)之间加入一条边权为\(w_i\)的边,如果这是第\(i\)个此种操作,则记这条新边为第\(i\)条。\(\centerdot\)将第\(k......
  • P9459 浴眼盯真 题解
    由于我不会使用正则表达式,所以我只能使用基础Python语法QwQ。[input().split()for_inrange(int(input()))]是个列表生成器,效果是产生一个长度为\(T\)的列表,列表的元素是以每一行以空格为分割符的字符串列表。for(a,b,c,d)in[]可以用\(a,b,c,d\)来复制列表中每个元素......
  • P9451 [ZSHOI-R1] 新概念报数 题解
    满足\(\operatorname{popcount}(x)<3\)的数实际上很少,直接把所有这些数扔到set里面,询问就返回set中\(x\)的下一个元素即可。记得开longlong。set内的元素数量是\(\log^2w\),所以复杂度是\(\mathcalO(\log^2w\log\log^2w+T\log\log^2w)=\mathcalO(\log^2w\log\logw......
  • 【题解】Luogu[P4711] 「化学」相对分子质量
    Link一道简单的模拟题,评绿可能有点高了。因为没有括号嵌套,难度瞬间降了一个档次,我们直接对着化学式扫一遍即可。若扫到左括号,说明接下来都是在括号内的,我们标记一下。若扫到大写字母,说明出现了一个新的元素,那么我们就看后面是否有下标,若有则类似于快读的方式直接处理后面的数......
  • [USACO13DEC] The Bessie Shuffle S 洗牌 题解
    提供一种思路,可以做到\(O(n)\)。目前是全OJ最优解,跑到了79ms。update2023.07.29完工,期望无bug(暑假快乐吖o( ̄▽ ̄)ブ)update2023.07.27(要原题检测了,先占个坑,有时间再补)原题大意P3095[USACO13DEC]TheBessieShuffleS有\(n\)张牌,每次取出\(m\;(m<n)\)张牌进行置换操作。操......
  • CF858C 题解
    洛谷链接&CF链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述给你一个均为小写字母的字符串,如果它的子串同时满足:三个连着的辅音字母。这一段连着的辅音字母不是全部一样的。就认为它不合法。现在要求用最少的空格隔开这个字符串,使得它变成......
  • AT_agc022_a 题解
    洛谷链接&Atcoder链接本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。题目简述给定字符串\(S\),仅包含互不相同的小写字母,你需要找到仅包含互不相同的小写字母的字符串中,第一个字典序比它大的字符串,如果找不到输出\(-1\)。(\(|S|\le26\))思路这篇题解......
  • 【题解】[2023牛客多校] Qu'est-ce Que C'est?
    题目传送门:[2023牛客多校]Qu'est-ceQueC'est?题意给定\(n,m\)构造\(a_{1},a_{2},...,a_{n}\),其中\(a_{i}\in[-m,m]\)之间取值。需要保证序列任意连续子段和都非负。\(0\leqn,m\leq5000\)分析记录合法序列的最小后缀。通过最小后缀来判断下一个数的取值范围。......
  • Codeforces Round 888 (Div. 3) 题解
    考场上\(7\)题做出来\(4\)题,最后几分钟才把D题调出来,但还是吃了不少罚时A.EscalatorConversations\(O(n)\)枚举即可,对于每个人计算需要的间隔台阶数是否在\((0,m)\)以内以及相差高度是否是\(k\)的倍数B.ParitySort显然,偶数和奇数是不可能产生交换操作的,而偶数......
  • P2679 [NOIP2015 提高组] 子串 题解
    原题\(题目大意\)\(从字符串a中选出k个子串s_1,s_2,s_3...s_k使得s_1+s_2+s_3+...+s_k=b\)\(求总方案数对10^9+7取模的结果\)\(1\le|a|即n\le1000,1\le|b|即m\le200,1\lek\le|b|\)\(设f_{i,j,x}表示已经选到a的第i个字符,b的第j个字符,共选了x个子串的方案数\)\(则可得......