首页 > 其他分享 >12.2闲话

12.2闲话

时间：2023-12-02 11:24:24浏览次数：43  
标签：ch int 闲话 top 12.2 dfn inline mathrm

树剖树剖

调了好久的板子终于过了，主要原因是建线段树出了问题，警钟长鸣

本来应该是t[q].dat=a[T[l].rnk];

然后我打的是t[q].dat=a[l];

DFS序2

点击查看代码 

#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    for(int i=1;i<N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    for(int i=1;i<=M;i++){
        int q=read();
        if(q==1){
            int x=read(),y=read();
            killTree::AddTree(x,y);
        }
        else{
            int x=read();
            std::cout<<killTree::AskTree(x)<<std::endl;
        }
    }
}

B.HAOI2015 树上操作

有一棵点数为 \(N\) 的树，以点 \(1\) 为根，且树点有边权。然后有 \(M\) 个
操作，分为三种：

操作 1 ：把某个节点 \(x\) 的点权增加 \(a\) 。
操作 2 ：把某个节点 \(x\) 为根的子树中所有点的点权都增加 \(a\) 。
操作 3 ：询问某个节点 \(x\) 到根的路径中所有点的点权和。

您一眼秒了它，这不是板子吗

点击查看代码 


#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=1;
    for(int i=1;i<=N;i++)
        a[i]=read();
    for(int i=1;i<N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    for(int i=1;i<=M;i++){
        int q=read();
        if(q==1){
            int x=read(),y=read();
            killTree::TreeAdd(x,x,y);
        }
        else if(q==2){
            int x=read(),y=read();
            killTree::AddTree(x,y);
        }
        else{
            int x=read();
            std::cout<<killTree::TreeSum(x,R)<<std::endl;
        }
    }
}

树剖其他操作

边权转点权

众所周知，树剖都是用的点权，但是有题目用边权怎么办(办不了)

好吧其实很简单

首先想一下树的性质:除了root以外的每个点有且只有一个父节点

所以有一个简单的方法

那就是把这个节点到父节点的边权记录为这个节点的点权，然后没了

但是有个注意的点

在区间\(\{\mathrm{T[x].dfn\sim T[y].dfn}\}\)中有一个点是尊贵的\(\mathrm{LCA(x,y)}\),这个点记录的是它与它父亲相连的边的权值,不在\(x,y\)的路径上

所以在查询/修改的时候，最后的区间是 \(\{\mathrm{T[x].dfn+1,T[y].dfn}\}\)

而且要判断 \(y\) 是不是\(\mathrm{LCA(x,y)}\),若是,则无需再查询/修改了

换根操作

一般树剖会有一个固定的root，所以只需剖一次就能找到所有需要的信息。

然而换根操作会改变根节点，使本来固定的信息变化。

然而，我们肯定不能每换一个根节点就重新剖一次，TLE警告，考虑只剖一次再依靠固定的信息来进行操作

树剖是靠 dfn 把一棵树变成序列，再靠线段树/树状数组维护。我们可以用 dfn 来实现换根

首先，要知道无论怎么换根都不会让路径改变(树的特性)

假设要访问最小值\(\mathrm{Treemin(x)}\) (设当前根节点为rootnow)

分类讨论

  • \(\mathrm{x=rootnow}\)

    直接输出整棵树的\(\min\)就行

  • \(\mathrm{x}\)不在\(\mathrm{rootnow}\)到原本的\(\mathrm{root}\)的路径里

    这样对\(\mathrm{x}\)的子树范围不存在影响，直接查询\(\mathrm{Treemin(x)}\)

  • \(\mathrm{x}\)在\(\mathrm{rootnow}\)到原本的\(\mathrm{root}\)的路径里

    这个是最恶心的()

    \(\mathrm{x}\)的\(\mathrm{son}\)中包含\(\mathrm{rootnow}\)的（设为\(\mathrm{ch}\)) 会变成\(\mathrm{x}\)的父节点，\(\mathrm{ch}\)兄弟节点不变，仍为\(\mathrm{x}\)的子节点，

    \(\mathrm{x}\)的父节点会变成\(\mathrm{x}\)的子节点，并且这个变化会从\(\mathrm{x}\)沿\(\mathrm x\)到\(\mathrm 1\)的路径，传递给路径上的每个节点。

    也就是说，相当于整棵以\(\mathrm 1\)为根的树，除去以\(\mathrm{ch}\)为根的子树，都变成了查询对象。

    我们考虑怎么求出\(\mathrm{ch}\)

    • 考虑跳链

      每次让深度大的点（\(x\))向上跳，如果 \(x\) 所在的重链的起点的父节点就是深度小的点（\(y\)），直接返回 \(x\) 所在重链的起点。

      跳到最后，\(x\) 就变成了LCA(\(x\),\(y\))（然而因为 \(x\) 在 \(y\) 的子树中其实就是swap(\(x\),\(y\)) ）

      并且 \(x\) 和 \(y\) 在一条重链上，所以 \(ch\) 就是 \(x\) 的重儿子，因为只有重儿子才会和父节点在一条重链上。

      接下来要判断 \(ch\) 的子树的范围，如果 \(ch\) 的子树已经到了 \(n\)，就不需要查询 \(dfn[ch] + size[ch]\) 到 \(n\) 了。

标签：ch,int,闲话,top,12.2,dfn,inline,mathrm
From： https://www.cnblogs.com/LuoTianYi66ccff/p/17871278.html

相关文章

  • 12.2
    均分纸牌P1031[NOIP2002提高组]均分纸牌-洛谷|计算机科学教育新生态(luogu.com.cn)这道题贪心没有想出来，有时间再看看。。。。。。。。。 砍龙头哈哈哈P2695骑士的工作-洛谷|计算机科学教育新生态(luogu.com.cn)这道题排序+贪心乱搞就行，然后发现了佬的解法，可......
  • 12.2每日总结
    final:Final用于修饰类、成员变量和成员方法。final修饰的类，不能被继承（String、StringBuilder、StringBuffer、Math，不可变类），其中所有的方法都不能被重写(这里需要注意的是不能被重写，但是可以被重载，这里很多人会弄混)，所以不能同时用abstract和final修饰类（abstract修饰的类是抽象类......
  • 文心一言 VS 讯飞星火 VS chatgpt （147）-- 算法导论12.2 2题
    二、用go语言，写出TREE-MINIMUM和TREE-MAXIMUM的递归版本。灵捷3.5。文心一言：以下是用Go语言编写的树的最大值和最小值的递归版本代码：packagemainimport("fmt")typeTreeNodestruct{ValintLeft*TreeNodeRight*TreeNode}......
  • 文心一言 VS 讯飞星火 VS chatgpt （146）-- 算法导论12.2 1题
    一、用go语言，假设一棵二叉搜索树中的结点在1到1000之间，现在想要查找数值为363的结点。下面序列中哪个不是查找过的序列?a.2，252，401，398，330，344，397，363。b.924，220，911，244，898，258，362，363。c.925，202，911，240，912，245，363。d.2，399，387，219，266，382，381，278，363。e.935，278，347，621，299，392，358，363。灵捷3......
  • 文心一言 VS 讯飞星火 VS chatgpt （146）-- 算法导论12.2 1题
    一、用go语言，假设一棵二叉搜索树中的结点在1到1000之间，现在想要查找数值为363的结点。下面序列中哪个不是查找过的序列?a.2，252，401，398，330，344，397，363。b.924，220，911，244，898，258，362，363。c.925，202，911，240，912，245，363。d.2，399，387，219，266，382，381，278，363。e.935，278，347，621，299，392，358，363。灵......
  • 2023-11-29 闲话 垃圾桶是这里吗
    算法竞赛学不了一点。刷点b站视频吧。纯纯当作水博客用，看再多哔哩哔哩也和研究怎么拍个照片让机器把力矩学了没有半毛钱关系是吧。昨天刷了一个参加IROS2022kyoto的分享。现在仍然有印象的几点是：advisor觉得他很social，问他有没有经验。他说大概可以先加入一些小团体......
  • 11.29闲话
    今天也是为了解LCA，然后学了树链剖分这边写个讲解树剖分为重链剖分和长链剖分通常指的是重链剖分重链剖分对于任意一个位于树上的节点重子节点表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。轻子节点表示剩余的所有子......
  • 11.28闲话
    今天突然想起来几句歌词便是我掏空予你一半心房也借你一半替我浅吟低唱纵然纸片凉薄爱轻狂虚妄你歌声里亦浸着我的痴放越想越难受所以...推歌纸片人【ilem投稿九周年】这是图片V4：佬啊,佬啊怎么是纸片儿啊调啊,调啊调的我心动啊佬啊,佬啊怎么是纸片儿呐调啊,......
  • 2023-11-28 闲话 无人之境
    http://www.stat.ucla.edu/~sczhu/research_blog.html昨天只读了文章千古事，得失寸心知的一篇，非常非常大收获。感觉比以前水的东西有意义多了。以后考虑多上各种大学网站上搜教授主页，看paper或者article都是不错的选择是吧。......
  • Cisco SD-WAN (Viptela) version 20.12.2 ED - 软件定义广域网
    CiscoSD-WAN(Viptela)version20.12.2ED-软件定义广域网请访问原文链接：https://sysin.org/blog/cisco-sd-wan-20/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org支持SASE的架构，其集成了面向多云、安全、统一通信和应用优化的各种功能，可用于轻松安全地将任何......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99