当前位置: 首页 > news >正文

[BZOJ]4817: [Sdoi2017]树点涂色

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

  Bob有一棵n个点的有根树,其中1号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。Bob可能会进行这几种操作:
  1 x:
  把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
  2 x y:
  求x到y的路径的权值。
  3 x y:
  在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。
  Bob一共会进行m次操作

Input

  第一行两个数n,m。
  接下来n-1行,每行两个数a,b,表示a与b之间有一条边。
  接下来m行,表示操作,格式见题目描述
  1<=n,m<=100000

Output

  每当出现2,3操作,输出一行。
  如果是2操作,输出一个数表示路径的权值
  如果是3操作,输出一个数表示权值的最大值

Sample Input

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

Sample Output

  3
  4
  2
  2

Solution

  发现这个修改操作像极了LCT,于是我们直接用LCT维护这棵树,每棵Splay代表一种颜色,每个点到根的权值就是到根路径上非偏爱边(这里非偏爱边相当于两端颜色不同的边)数量加一,一开始所有点的权值就是深度,当进行access操作时,我们每把一条偏爱边设成非偏爱边,就让这条边下面那棵子树权值加一,反之减一,以dfs序建线段树维护最大值即可,1操作直接access一遍,2操作等同于询问链上非偏爱边数加一,链上非偏爱边数即x到根的非偏爱边数+y到根的非偏爱边数-2*lca(x,y)到根的偏爱边数,3操作直接查。由于LCT是均摊O(nlogn)的,我们往里面每次操作都加了一个维护线段树的工作,总复杂度O(nlogn^2)。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
char B[1<<26],*S=B,C;int X;
inline int read()
{
    while((C=*S++)<'0'||C>'9');
    for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=X*10+C-'0';
    return X;
}
#define MN 100000
#define LG 17
struct edge{int nx,t;}e[MN*2+5];
int h[MN+5],en,fa[LG][MN+5],d[MN+5],a[MN+5],l[MN+5],r[MN+5],cnt;
inline void ins(int x,int y)
{
    e[++en]=(edge){h[x],y};h[x]=en;
    e[++en]=(edge){h[y],x};h[y]=en;
}
namespace segtree
{
    #define L (k<<1)
    #define R (k<<1|1)
    struct node{int l,r,mx,mk;}t[MN*4+5];
    inline void up(int k){t[k].mx=max(t[L].mx,t[R].mx);}
    inline void mark(int k,int x){t[k].mx+=x;t[k].mk+=x;}
    inline void down(int k){if(t[k].mk)mark(L,t[k].mk),mark(R,t[k].mk),t[k].mk=0;}
    void build(int k,int l,int r)
    {
        if((t[k].l=l)==(t[k].r=r)){t[k].mx=a[l];return;}
        int mid=l+r>>1;
        build(L,l,mid);build(R,mid+1,r);up(k);
    }
    void add(int k,int l,int r,int x)
    {
        if(t[k].l==l&&t[k].r==r){mark(k,x);return;}
        int mid=t[k].l+t[k].r>>1;down(k);
        if(r<=mid)add(L,l,r,x);
        else if(l>mid)add(R,l,r,x);
        else add(L,l,mid,x),add(R,mid+1,r,x);
        up(k);
    }
    int query(int k,int l,int r)
    {
        if(t[k].l==l&&t[k].r==r)return t[k].mx;
        int mid=t[k].l+t[k].r>>1;down(k);
        if(r<=mid)return query(L,l,r);
        if(l>mid)return query(R,l,r);
        return max(query(L,l,mid),query(R,mid+1,r));
    }
}
namespace lct
{
    #define L(x) c[x][0]
    #define R(x) c[x][1]
    int fa[MN+5],c[MN+5][2],ll[MN+5];
    inline void up(int x){ll[x]=L(x)?ll[L(x)]:x;}
    inline bool isc(int x){return L(fa[x])==x||R(fa[x])==x;}
    void rotate(int x)
    {
        int f=fa[x],ff=fa[f],l=R(f)==x,r=l^1;
        if(isc(f))c[ff][R(ff)==f]=x;
        fa[f]=x;fa[x]=ff;fa[c[x][r]]=f;
        c[f][l]=c[x][r];up(c[x][r]=f);
    }
    void splay(int x)
    {
        for(int f;isc(x);rotate(x))
            if(isc(f=fa[x]))rotate(L(fa[f])==f^L(f)==x?x:f);
        up(x);
    }
    void access(int x)
    {
        for(int i=0,p;x;x=fa[i=x])
        {
            splay(x);
            if(R(x))segtree::add(1,l[ll[R(x)]],r[ll[R(x)]],1);
            if(i)segtree::add(1,l[ll[i]],r[ll[i]],-1);
            R(x)=i;
        }
    }
}
void dfs(int x)
{
    a[l[x]=++cnt]=d[x];
    for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa[0][x])
        lct::fa[e[i].t]=fa[0][e[i].t]=x,d[e[i].t]=d[x]+1,dfs(e[i].t);
    r[x]=cnt;
}
int lca(int x,int y)
{
    int dx=d[x]-d[y],i;
    if(dx<0)swap(x,y),dx=-dx;
    for(i=0;dx;++i,dx>>=1)if(dx&1)x=fa[i][x];
    if(x==y)return x;
    for(i=LG;i--;)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
int main()
{
    fread(B,1,1<<26,stdin);
    int n,m,i,j,x,y,z;
    n=read();m=read();
    for(i=1;i<n;++i)ins(read(),read());
    dfs(1);segtree::build(1,1,n);
    for(i=1;i<LG;++i)for(j=1;j<=n;++j)fa[i][j]=fa[i-1][fa[i-1][j]];
    using segtree::query;
    while(m--)
    {
        i=read();
        if(i==1)lct::access(read());
        if(i==2)z=lca(x=read(),y=read()),
            printf("%d\n",query(1,l[x],l[x])+query(1,l[y],l[y])-(query(1,l[z],l[z])<<1)+1);
        if(i==3)x=read(),printf("%d\n",query(1,l[x],r[x])+1);
    }
}

转载于:https://www.cnblogs.com/ditoly/p/BZOJ4817.html

相关文章:

  • redis和memcahed的共同点,区别以及应用场景
  • mysql 去除密码登录
  • express中的路径区别
  • 团队作业2——需求分析原型设计
  • redis五种数据类型的实现方式,常用命令,应用场景
  • MVC前后台传值
  • idea 右键没有run和debug选项
  • 浏览器渲染优化4(styles and layout)
  • leetcode 98,判断二叉树为BST
  • redis bind not error
  • lua实现热更方式
  • 元素
  • 基础面试题:面向对象和面向过程的区别,性能对比
  • 基础面试题: JDK 和 JRE
  • 基础面试题:java内存区域
  • Android单元测试 - 几个重要问题
  • Android开源项目规范总结
  • canvas 高仿 Apple Watch 表盘
  • CentOS7简单部署NFS
  • crontab执行失败的多种原因
  • Docker 1.12实践:Docker Service、Stack与分布式应用捆绑包
  • ECMAScript 6 学习之路 ( 四 ) String 字符串扩展
  • ES6--对象的扩展
  • Flannel解读
  • iOS高仿微信项目、阴影圆角渐变色效果、卡片动画、波浪动画、路由框架等源码...
  • Laravel深入学习6 - 应用体系结构:解耦事件处理器
  • Linux编程学习笔记 | Linux多线程学习[2] - 线程的同步
  • mysql 数据库四种事务隔离级别
  • socket.io+express实现聊天室的思考(三)
  • 从0实现一个tiny react(三)生命周期
  • 翻译:Hystrix - How To Use
  • 看完九篇字体系列的文章,你还觉得我是在说字体?
  • ​​​​​​​​​​​​​​Γ函数
  • ​一文看懂数据清洗:缺失值、异常值和重复值的处理
  • #我与Java虚拟机的故事#连载16:打开Java世界大门的钥匙
  • #我与虚拟机的故事#连载20:周志明虚拟机第 3 版:到底值不值得买?
  • (ZT)薛涌:谈贫说富
  • (二)c52学习之旅-简单了解单片机
  • (分布式缓存)Redis哨兵
  • (六)什么是Vite——热更新时vite、webpack做了什么
  • (五)IO流之ByteArrayInput/OutputStream
  • (循环依赖问题)学习spring的第九天
  • (转)淘淘商城系列——使用Spring来管理Redis单机版和集群版
  • (最简单,详细,直接上手)uniapp/vue中英文多语言切换
  • ***测试-HTTP方法
  • .CSS-hover 的解释
  • .gitignore
  • .Net Attribute详解(上)-Attribute本质以及一个简单示例
  • .NET和.COM和.CN域名区别
  • [ CTF ] WriteUp-2022年春秋杯网络安全联赛-冬季赛
  • [ vulhub漏洞复现篇 ] ThinkPHP 5.0.23-Rce
  • []T 还是 []*T, 这是一个问题
  • [AUTOSAR][诊断管理][ECU][$37] 请求退出传输。终止数据传输的(上传/下载)
  • [C#]DataTable常用操作总结【转】
  • [CISCN2019 华东南赛区]Web4