首页 > 其他分享 >题解:P6351 [PA2011] Hard Choice

题解:P6351 [PA2011] Hard Choice

时间:2024-09-24 16:37:10浏览次数:10  
标签:node rt ch 题解 void Hard Choice fa root

题意

维护一张无向图,要求支持以下操作:

  • 切断一条边。
  • 查询两个点是否有有两条完全不同的路径相连。

分析

因为断边操作不好维护,考虑离线后将断边变为加边。

因此,我们只需要维护加边操作即可。

考虑使用 LCT。

首先,因为涉及到边权,套路地用节点代替边。

如果某一条边连接的两个点属于两个不同的连通块,那么直接连边。

如果一条边连接的两个点属于同一个连通块,我们可以在它所连接的两点的路径上将所有的节点的权值 \(+1\),表示这些节点可以由两条路径连接。

查询的时候,如果两点之间的所有节点的权值都大于 \(1\),那么就满足,否则不满足。

所以我们只需要支持区间加和查询最小值即可。

Code

#include<bits/stdc++.h>
using namespace std;

namespace LCT
{
    struct node
    {
        node *ch[2], *fa;
        bool rev;
        int v, mn, tag;
        node(int x=0) {v=x, mn=x, rev=0, ch[0]=ch[1]=fa=0, tag=0;}
        bool not_root() {return fa&&(fa->ch[0]==this||fa->ch[1]==this);}
        bool is_rson() {return this==fa->ch[1];}
        void reverse() {rev^=1;swap(ch[0], ch[1]);}
        void add(int w) {tag+=w; mn+=w; v+=w;}
        void push_up()
        {
            mn=v;
            if(ch[0]) mn=min(mn, ch[0]->mn);
            if(ch[1]) mn=min(mn, ch[1]->mn);
        }
        void push_down() 
        {
            if(rev) 
            {
                if(ch[0]) ch[0]->reverse();
                if(ch[1]) ch[1]->reverse();
                rev^=1;
            }
            if(tag)
            {
                if(ch[0]) ch[0]->add(tag);
                if(ch[1]) ch[1]->add(tag);
                tag=0;
            }
        }
    };

    void rotate(node *x)
    {
        bool k=x->is_rson();
        node *y=x->fa, *z=y->fa, *w=x->ch[!k];
        if(y->not_root()) z->ch[y->is_rson()]=x;
        x->ch[!k]=y, y->ch[k]=w;
        y->fa=x, x->fa=z;
        if(w) w->fa=y;
        y->push_up();
        x->push_up();
    }

    stack<node*> s;

    void splay(node *x)
    {
        s.emplace(x);
        while(s.top()->not_root()) s.emplace(s.top()->fa);
        while(!s.empty()) s.top()->push_down(), s.pop();
        while(x->not_root())
        {
            if(x->fa->not_root())
                rotate((x->is_rson()^x->fa->is_rson())?x:x->fa);
            rotate(x);
        }
    }
    
    void access(node *x)
    {
        for(node *y=0;x;x=(y=x)->fa) 
            splay(x), x->ch[1]=y, x->push_up();
    }

    void make_root(node *x)
    {
        access(x); 
        splay(x); 
        x->reverse();
    }

    node *find_root(node *x)
    {
        access(x); 
        splay(x); 
        while(x->push_down(), x->ch[0]) 
            x=x->ch[0];
        return x;
    }

    void link(node *x, node *y)
    {
        if(find_root(x)!=find_root(y)) 
            make_root(x), x->fa=y;
    }

    void cut(node *x, node *y)
    {
        make_root(x); 
        access(y); 
        splay(y); 
        if(y->ch[0]==x) y->ch[0]=x->fa=0;
    }

    int query(node *x, node *y)
    {
        make_root(x);
        access(y);
        splay(y);
        return y->mn;
    }

    void modify(node *x, node *y)
    {
        make_root(x);
        access(y);
        splay(y);
        y->add(1);
    }
}

set<pair<int, int>> s;
LCT::node *rt[100005];
vector<tuple<int, int, int>> vc;
vector<bool> ans;

int main()
{
    int n, m, q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) rt[i]=new LCT::node;
    for(int i=1, u, v;i<=m;i++)
    {
        cin>>u>>v;
        if(u>v) swap(u, v);
        s.emplace(u, v);
    }
    char c;
    for(int i=1, x, y;i<=q;i++)
    {
        cin>>c>>x>>y;
        if(c=='Z') 
        {
            vc.emplace_back(1, x, y);
            if(x>y) swap(x, y);
            s.erase({x, y});
        }
        if(c=='P') vc.emplace_back(2, x, y);
    }
    for(auto [u, v]:s)
    {
        if(find_root(rt[u])==find_root(rt[v]))
            modify(rt[u], rt[v]);
        else 
        {
            LCT::node *eg=new LCT::node;
            link(rt[u], eg), link(eg, rt[v]);
        }
    }
    for(auto [op, u, v]:views::reverse(vc))
    {
        if(op==1)
        {
            if(find_root(rt[u])==find_root(rt[v]))
                modify(rt[u], rt[v]);
            else 
            {
                LCT::node *eg=new LCT::node;
                link(rt[u], eg), link(eg, rt[v]);
            }
        }
        else
        {
            int w=0;
            if(find_root(rt[u])==find_root(rt[v]))
                w=query(rt[u], rt[v]);
            ans.emplace_back(w);
        }
    }
    for(auto op:views::reverse(ans))
        cout<<(op?"TAK\n":"NIE\n");
}

标签:node,rt,ch,题解,void,Hard,Choice,fa,root
From: https://www.cnblogs.com/redacted-area/p/18429467

相关文章

  • ABC245G Foreign Friends 题解 / 二进制分组
    ABC245GForeignFriends题解回顾一下二进制分组。题目大意给定一张\(N\)个点\(M\)条边的无向图,及\(L\)个特殊点。每个点有颜色\(C_i\)。求每个点到离他最近的与他颜色不同特殊点的距离。Solve两个点颜色不同,等价于他们的颜色在二进制下至少有一位不同。所以我们考......
  • MySQL GROUP BY 分区大小写问题解析
    在数据库操作中,GROUPBY是一个常用的SQL语句,用于根据一个或多个列的值对结果集进行分组。然而,在使用MySQL时,你可能会遇到一个常见问题:大小写敏感性。本文将探讨MySQL中GROUPBY的大小写敏感性问题,并提供一些解决方案。什么是大小写敏感性?在计算机科学中,大小写敏感性是指......
  • git reset --hard执行之后怎么撤回
    情况一,执行reset命令前commit过根据你的gitreflog输出,显示你最近的操作是:HEAD@{0}:gitreset--hardHEAD,即你重置到了当前的HEAD。HEAD@{1}:这是你克隆仓库时的记录。由于HEAD@{0}和HEAD@{1}都指向相同的提交f776dba,这意味着你在执行gitreset--hard之前和之后......
  • Codeforces Round 974 (Div.3) 题解
    CodeforcesRound974(Div.3)题解A.RobinHelps模拟按照题意模拟即可。voidShowball(){intn,k;cin>>n>>k;intcur=0,ans=0;for(inti=0;i<n;i++){intx;cin>>x;if(x>=k)cur+=x;elseif(!x){if(cur>=1)cu......
  • AT_jsc2021_g Spanning Tree 题解
    感觉自己稍微有一点唐了。思路我们首先可以把一定要连的边连起来。这样就变成了一个无向图生成树计数问题。如何求解。使用矩阵树定理!我们可以求出基尔霍夫矩阵,然后跑一遍行列式就可以了。时间复杂度:\(O(n^3)\)。Code#include<bits/stdc++.h>usingnamespacestd;con......
  • Count Equation Solutions 题解
    前言题目链接:洛谷;UVA。题意简述求以下方程解的个数:\[a_1x_1-a_2x_2+a_3x_3-a_4x_4+a_5x_5-a_6x_6=0\]其中\(1\leqx_i\leqm\leq10^2\),\(x_i\in\mathbb{Z}\),多测。题目分析把\(a_2,a_4,a_6\)变成其相反数,变成\(\sum\limits_{i=1}^6a......
  • 题解 [ARC184B] 123 Set
    个人认为思维难点相同的三倍经验:P3226[HNOI2012]集合选数、TFSETS-Triple-FreeSets。区别在于状压DP的方法。我们称不包含质因子\(2\)和\(3\)的数为\(2,3\texttt{-Free}\)的。对于\([1,n]\)内每个\(2,3\texttt{-Free}\)的整数\(u\),可以列出以下的矩阵:\[\begi......
  • NEERC2013题解
    B.BonusCards简单dp一下,记\(f_{ij}\)为前i次有j次分给第一类的概率。最后再算上我在第一类被选上的概率即可。constintN=3005;#defineintlonglongintn,a,b;doublef[N][N],g[N][N];signedmain(void){#ifdefONLINE_JUDGE freopen("bonus.in","r",stdin......
  • 题解:CF888G Xor-MST
    题解:CF888GXor-MST题目大意:给定\(n\)个点的点权,任意两点间边权是点权的异或和。求这张完全图的MST的权值。思路:Boruvka+Trie树+按位贪心。关键就在于如何求出Boruvka中的best数组。考虑对点权建trie树,对于节点\(i\)本轮的连边,就是找“和它最相似”的那......
  • SP1825 FTOUR2 - Free tour II 题解
    题目传送门前置知识点分治|树状数组解法维护点对信息,考虑点分治。本题比luoguP4149[IOI2011]Race多了个前缀查询\(\max\)。套个支持单点修改、区间查询\(\max\)的数据结构即可。直接线段树维护区间\(\max\)貌似会TLE,换成树状数组维护前缀\(\max\)即可。注......