【luogu P3979 遥远的国度】题解

题目链接：https://www.luogu.org/problemnew/show/P3979

除了换根操作都是裸的树剖

所以换根时考虑：

1.我查询的根等于换的根：无影响

2.我查询的根是换的根的子树：无影响

3.我查询的根是换的根的祖先：查询除换的根及其往上直到为要查询的根的第一层儿子的祖先(设为S)的子树以外的所有节点 (此时满足seg[S] <= seg[root] <= seg[S]+size[S]-1)

求LCA 查询1到seg[S]-1 和 seg[S]+size[S]到n 正好避开子树seg[S] 到 seg[S]+size[S]-1

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define lson left, mid, rt<<1

#define rson mid + 1, right, rt<<1|1

using namespace std;

const ll maxn = 200000 + 10;

ll tree[maxn<<2], lazy[maxn<<2];

ll seg[maxn], fa[maxn], size[maxn], rev[maxn], son[maxn], deep[maxn], top[maxn], num;

ll node[maxn], res, n, m, root, r;

struct edge{

    ll from, to, next;

}e[maxn<<2];

ll head[maxn], cnt;

void add(ll u, ll v)

{

    e[++cnt].from = u;

    e[cnt].next = head[u];

    e[cnt].to = v;

    head[u] = cnt;

}

//--------------------------segment_tree

void PushUP(ll rt)

{

    tree[rt] = min(tree[rt<<1], tree[rt<<1|1]);

}

void build(ll left, ll right, ll rt)

{

    if(left == right)

    {

        tree[rt] = rev[left];

        return;

    }

    ll mid = (left + right)>>1;

    build(lson);

    build(rson);

    PushUP(rt);

}

void PushDOWN(ll rt)

{

    lazy[rt<<1] = lazy[rt];

    lazy[rt<<1|1] = lazy[rt];

    tree[rt<<1] = lazy[rt];

    tree[rt<<1|1] = lazy[rt];

    lazy[rt] = 0;

}

void update(ll l, ll r, ll add, ll left, ll right, ll rt)

{

    if(l <= left && r >= right)

    {

        tree[rt] = add;

        lazy[rt] = add;

        return;

    }

    ll mid = (left + right)>>1;

    if(lazy[rt]) PushDOWN(rt);

    if(l <= mid) update(l, r, add, lson);

    if(r > mid) update(l, r, add, rson);

    PushUP(rt);

}

ll query(ll l, ll r, ll left, ll right, ll rt)

{

    ll res = 0x7fffffff;

    if(l <= left && r >= right)

    {

        return tree[rt];

    }

    ll mid = (left + right)>>1;

    if(lazy[rt]) PushDOWN(rt);

    if(l <= mid) res = min(res, query(l, r, lson));

    if(r > mid) res = min(res, query(l, r, rson));

    return res;

}

//------------------------

void dfs1(ll u, ll f, ll d)

{

    ll maxson = -1;

    size[u] = 1;

    deep[u] = d;

    fa[u] = f;

    for(ll i = head[u]; i != -1; i = e[i].next)

    {

        ll v = e[i].to;

        if(f != v)

        {

            dfs1(v, u, d+1);

            size[u] += size[v];

            if(size[v] > maxson) son[u] = v, maxson = size[v];

        }

    }

}

void dfs2(ll u, ll t)

{

    seg[u] = ++num;

    rev[num] = node[u];

    top[u] = t;

    if(!son[u]) return;

    dfs2(son[u], t);

    for(ll i = head[u]; i != -1; i = e[i].next)

    {

        ll v = e[i].to;

        if(v == son[u] || v == fa[u]) continue;

        dfs2(v,v);

    }

}

/*ll qRange(ll x, ll y)

{

    ll ans = 0;

    while(top[x] != top[y])

    {

        if(deep[top[x]] < deep[top[y]]) swap(x, y);

        res = 0;

        res = query(seg[top[x]], seg[x], 1, n, 1);

        ans = (ans + res);

        x = fa[top[x]];

    }

    if(deep[x] > deep[y]) swap(x, y);

    res = 0;

    res = query(seg[x], seg[y], 1, n, 1);

    ans = (ans + res);

    return ans;

}*/

void updRange(ll x, ll y, ll k)

{

    while(top[x] != top[y])

    {

        if(deep[top[x]] < deep[top[y]]) swap(x, y);

        update(seg[top[x]], seg[x], k, 1, n, 1);

        x = fa[top[x]];

    }

    if(deep[x] > deep[y]) swap(x, y);

    update(seg[x], seg[y], k, 1, n, 1);

}

ll LCA(int x, int y)

{

    while(top[x] != top[y])

    {

        if(deep[top[x]] < deep[top[y]]) swap(x, y);

        x = fa[top[x]];

    }

    return deep[x] < deep[y] ? x : y;

}

ll qSon(ll x)

{

    if(x == r)

    return query(1, n, 1, n, 1);

    int p = LCA(r, x);

    if(p != x)

    return query(seg[x], seg[x]+size[x]-1, 1, n, 1);

    int S;

    for(int i = head[x]; i != -1; i = e[i].next)

    {

        int v = e[i].to;

        if(seg[v] <= seg[r] && seg[r] <= seg[v] + size[v] -1 && v != fa[x])

        {

            S = v; break;

        }

    }

    return min(query(1, seg[S]-1, 1, n, 1), query(seg[S]+size[S], n, 1, n, 1));

}

int main()

{

    memset(head, -1, sizeof(head));

    scanf("%lld%lld",&n,&m);

    for(ll i = 1; i < n; i++)

    {

        ll u, v;

        scanf("%lld%lld",&u,&v);

        add(u, v), add(v, u);

    }

    for(ll i = 1; i <= n; i++)

    scanf("%lld",&node[i]);

    scanf("%lld",&root);

    dfs1(root, 0, 1);

    dfs2(root, root);

    build(1,n,1);

    r = root;

    for(ll i = 1; i <= m; i++)

    {

        ll opt, x, y, z;

        scanf("%lld",&opt);

        if(opt == 1)

        {

        	scanf("%lld",&x);

        	r = x;

        }

        if(opt == 2)

        {

            scanf("%lld%lld%lld",&x,&y,&z);

            updRange(x, y, z);

        }

        if(opt == 3)

        {

            scanf("%lld",&x);

            printf("%lld\n",qSon(x));

        }

    }

    return 0;

}

巴特西

【luogu P3979 遥远的国度】题解

最新文章

热门文章

巴特西

【luogu P3979 遥远的国度】 题解

最新文章

热门文章

【luogu P3979 遥远的国度】题解