4817 [Sdoi2017]树点涂色
阅读原文时间:2023年07月13日阅读:2

Bob 有一棵 n 个点的有根树,其中 1 号点是根节点。Bob 在每个点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob可能会进行这几种操作:

  • 1 x 表示把点 x 到根节点的路径上所有的点染上一种没有用过的新颜色。
  • 2 x y 求 x 到 y 的路径的权值。
  • 3 x 在以 x 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob一共会进行 m 次操作

第一行两个数 n,m。

接下来 n−1 行,每行两个数 a,b 表示 a 与 b 之间有一条边。

接下来 m 行,表示操作,格式见题目描述

每当出现 2,3 操作,输出一行。

如果是 2 操作,输出一个数表示路径的权值

如果是 3 操作,输出一个数表示权值的最大值

输入 #1

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

输出 #1

3
4
2
2

\(n , m <= 1e5\)

分析

将相同颜色的点看做一个Splay , 那么操作1就是标准的access

对于操作二三维护,一个点到根的颜色个数,也是Splay的个数。

这个可以用线段树维护

在assess操作时,将要并上去的的子树-- , 断开的子树++

注意

1.别忘了初始化,初始时各个节点颜色互不相同,也就是ans = d(到根的距离)
2.rot时分清谁和谁, 我脑残写了 fa[x] = y , fa[y] = x

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 210000;
inline int read()
{
    register int x = 0; register char c = getchar();
    while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
    return x;
}
int n , m , dfn , cnt;
int head[N] , st[N] , ed[N] , d[N] , fdfn[N] , f[N][20] , siz[N] , fa[N] , tr[N][2] , rev[N] , maxn[N<<2] , tag[N<<2];
struct edge{int v , nex; } e[N<<1];
inline void add(int u , int v) { e[++cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt; return ; }
#define D_bag puts("this is OK!!");
// Segment_tree->begin()

void Down(int k)
{
    if(tag[k])
    {
        maxn[k<<1] += tag[k]; maxn[k<<1|1] += tag[k];
        tag[k<<1] += tag[k]; tag[k<<1|1] += tag[k]; tag[k] = 0; // tag -->clear
    }
    return ;
}

void build(int k , int l , int r) // 建树初始化
{
    if(l == r)
    {
        maxn[k] = d[fdfn[l]];
        return ;
    }
    int mid = (l + r) >> 1;
    build(k << 1 , l , mid);
    build(k << 1 | 1 , mid + 1 , r);
    maxn[k] = max(maxn[k<<1] , maxn[k<<1|1]);
    return ;
}

void Change(int k , int l , int r , int x , int y , int val)
{
    if(x <= l && r <= y) return (void)(maxn[k] += val , tag[k] += val);
    int mid = (l + r) >> 1; Down(k);
    if(x <= mid) Change(k << 1 , l , mid , x , y , val);
    if(y  > mid) Change(k << 1 | 1 , mid+1 , r , x , y , val);
    maxn[k] = max(maxn[k<<1] , maxn[k<<1|1]); return ;
}

int Ask(int k , int l , int r , int x , int y)
{
    if(x <= l && r <= y) return maxn[k];
    Down(k); int mid = (l + r) >> 1 , ans = 0;
    if(x <= mid) ans = max(ans , Ask(k<<1 , l , mid , x , y));
    if(y  > mid) ans = max(ans , Ask(k<<1|1 , mid+1 , r , x , y));
    return ans;
}

// Segment_tree->end()

inline int witch(int x) { return x == tr[fa[x]][1]; }
inline int nrt(int x) { return (fa[x] && (tr[fa[x]][0] == x || tr[fa[x]][1] == x)); }
void rot(int x)
{
    int y = fa[x] , z = fa[y] , k = witch(x) , w = tr[x][!k];
    if(nrt(y)) tr[z][witch(y)] = x; fa[x] = z; // !!!!
    tr[y][k] = w; if(w) fa[w] = y;
    tr[x][!k] = y; fa[y] = x;
}

void Splay(int x)
{
    while(nrt(x))
    {
        if(nrt(fa[x])) rot(witch(x) == witch(fa[x]) ? fa[x] : x);
        rot(x);
    }
    return ;
}

int find_son(int x)
{
    while(tr[x][0]) x = tr[x][0]; return x;
}

void assess(int x)
{
    int t = 0;
    for(t = 0; x ; t = x , x = fa[x])
    {
        Splay(x);
        if(t)
        {
            int son = find_son(t);
            Change(1 , 1 , n , st[son] , ed[son] , -1);
        }
        if(tr[x][1])
        {
            int son = find_son(tr[x][1]);
            Change(1 , 1 , n , st[son] , ed[son] , 1);
        }
        tr[x][1] = t;
    }
    return ;
}

int lca(int x , int y)
{
    if(x == y) return x;
    if(d[x] < d[y]) swap(x , y);
    for(int i = 18 ; i >= 0 ; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = 18 ; i >= 0 ; --i) if(f[x][i] != f[y][i]) x = f[x][i] , y = f[y][i];
    return f[x][0];
}

void dfs(int x)
{
    st[x] = ++dfn; fdfn[dfn] = x;
    for(int i = 1 ; i <= 18 ; ++i) f[x][i] = f[f[x][i-1]][i-1];
    for(int i = head[x] , v; i ; i = e[i].nex)
    {
        v = e[i].v;
        if(v == f[x][0]) continue;
        f[v][0] = x; d[v] = d[x] + 1; fa[v] = x; dfs(v);
    }
    ed[x] = dfn;
    return ;
}
int main()
{
    n = read(); m = read();
    for(int i = 1 , a , b; i <= n - 1 ; ++i)
    {
        a = read(); b = read();
        add(a , b); add(b , a);
    }
    d[1] = 1; dfs(1);
    build(1 , 1 , n);
    for(int i = 1 , op , x ; i <= m ; ++i)
    {
        op = read(); x = read();
        if(op == 1) assess(x);
        else
        if(op == 2)
        {
            int y = read() , p = lca(x , y);
            int ans = Ask(1 , 1 , n , st[x] , st[x]) + Ask(1 , 1 , n , st[y] , st[y]) - 2 * Ask(1 , 1 , n , st[p] , st[p]) + 1;
            printf("%d\n" , ans);
        }
        else
        if(op == 3)
            printf("%d\n" , Ask(1 , 1 , n , st[x] , ed[x]));
    }
    return 0;
}
/*
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
*/
  1. BZOJ 4817 [SDOI2017]树点涂色 (LCT+线段树维护dfs序)

    题目大意:略 涂色方式明显符合$LCT$里$access$操作的性质,相同颜色的节点在一条深度递增的链上 用$LCT$维护一个树上集合就好 因为它维护了树上集合,所以它别的啥都干不了了 发现树是静态的 …

  2. bzoj 4817: [Sdoi2017]树点涂色

    Description Bob有一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.定义一条路 径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色. …

  3. 【刷题】BZOJ 4817 [Sdoi2017]树点涂色

    Description Bob有一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.定义一条路 径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色. …

  4. BZOJ 4817: [Sdoi2017]树点涂色(LCT+树剖+线段树)

    题目描述 Bob有一棵 nn 个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同. 定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色. Bob …

  5. BZOJ 4817: [Sdoi2017]树点涂色 LCT+Access的性质+DFS序+线段树

    Code: #include #define maxn 200003 #define inf -1000000 using namespace std; vo …

  6. BZOJ.4817.[SDOI2017]树点涂色(LCT DFS序 线段树)

    题目链接 操作\(1.2\)裸树剖,但是操作\(3\)每个点的答案\(val\)很不好维护.. 如果我们把同种颜色的点划分到同一连通块中,那么向根染色的过程就是Access()! 最初所有点间都是虚边 …

  7. bzoj 4817: [Sdoi2017]树点涂色 LCT+树链剖分+线段树

    题目: Bob有一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同. 定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色. Bob可能会进 …

  8. bzoj 4817: [Sdoi2017]树点涂色【树链剖分+LCT】

    非常妙的一道题. 首先对于操作一"把点x到根节点的路径上所有的点染上一种没有用过的新颜色",长得是不是有点像LCT中的access操作?进而发现,如果把同一颜色的点连起来作为LCT …

  9. BZOJ 4817 [Sdoi2017]树点涂色 ——LCT 线段树

    同BZOJ3779. SDOI出原题,还是弱化版的. 吃枣药丸 #include #include #include # …

  10. 【WPF学习】第十八章 多点触控输入

    多点触控(multi-touch)是通过触摸屏幕与应用程序进行交互的一种方式.多点触控输入和更传统的基于笔(pen-based)的输入的区别是多点触控识别手势(gesture)——用户可移动多根手指以 …

  11. STT-MRAM存在的两个弊端

    随着自旋转移矩效应的发现以及材料和结构的优化,基于自旋转移矩效应的STT-MRAM器件应运而生.自从自旋转移矩效应被证实以来,一方面研究人员通过大量的努力尝试降低磁化反转的临界电流,增加热稳定性:另一 …

  12. 有关配置网站时安装ZipArache的方法。

    在配置网站初始化过程中,发现ZipArache需要启动,上网搜索了一番,发现安装ZipArache的步骤十分繁琐. 换一种思路,ZipArache作为PHP的拓展类,其名字首部有ZIP字样,那么可否直 …

  13. vector内存分配简单介绍

    众所周知,vector的size()其实并不代表它占用的空间,它实际占用空间可以用capacity()查看 众所周知,push_back()时,如果size==capacity则会使capacity从 …

  14. PTA Is Topological Order

    Write a program to test if a give sequence Seq is a topological order of a given graph Graph. Format …

  15. [P5748] 集合划分计数 - 生成函数,NTT

    求 \(10^5\) 以内的所有贝尔数:将 \(n\) 个有标号的球划分为若干非空集合的方案数 Solution 非空集合的指数生成函数为 \(F(x)=e^x-1\) 枚举一共用多少个集合,答案就是 …

  16. 42.通过原生SQL语句进行操纵mysql数据库

    views.py文件中: from django.shortcuts import render # 导入connection模块 from django.db import connection d …

  17. srpingboot web - 启动(3) 监听器

    接上一篇 一. getRunListeners() 在run() 方法中调用了 getRunListeners(args) 方法, 先看一下这个方法干了什么 private SpringApplica …

  18. Java设计模式(二)设计模式原则

    学习Java设计模式之前,有必要先了解设计模式原则. 开闭原则 定义 一个软件实体如类.模块和函数应该对扩展开放,对修改关闭 用抽象构建框架,用实现扩展细节 优点:提高软件系统的可复用性及可维护性 C …

  19. 【32】Padding(填充)原理讲解

    Padding 为了构建深度神经网络,你需要学会使用的一个基本的卷积操作就是padding,让我们来看看它是如何工作的.   我们在之前笔记中看到,如果你用一个3×3的过滤器卷积一个6×6的图像,你最 …

热门专题

pjsip和exosip

sql server2012数据库变成可疑

css animation 不想让子元素运动

打印hello world用的函数

rockwork软件安装教程

fast安装nginx

gitlab 界面master合并多个分支

django将csv展示在网页上

opencv的flags

cmd 命令行打开wps

@AutoConfigureBefore name属性

单点登录中https报500

lvgl 矩阵按钮字体左对齐

Python基于CRNN&CTPN的文本检测系统

mongodb用于统计文档条数对命令关键词

如何查看当前的flask版本

sockjs-client、stompjs

@windicss-devtools-update 请求

window下SVN标记添加如何把文件夹下面的所有文件都添加

批量ping工具检测是否丢包

Home

Powered By WordPress