洛谷P4332 [SHOI2014]三叉神经树(LCT)

时间:2022-09-15 19:40:18

传送门

FlashHu大佬太强啦%%%

首先,我们可以根据每一个点的权值为$1$的儿子的个数把每个点记为$0~3$,表示这一个点的点权

先考虑一下暴力的过程,假设从$0$变为$1$,先更改一个叶子结点,然后不断地往上更新,如果更改之后父亲的儿子中权值为$1$的儿子个数大于权值为$0$的儿子个数,那么就继续更新父亲,直到不能更新为止

不难发现,我们每一个更改的都是树上的一条链。而且,只有当点权为$1$时,才能因为修改使点权变为$2$,使输出改变,从而更新祖先。那么,我们需要的就是对于每一个节点,从它向上的连续的点权为$1$的一部分

如果是从$1$变为$0$同理,我们要维护从每一个节点向上的连续的点权为$2$的一部分

那么我们对于每一个节点,先access,然后记录splay中最深的点权不为$1$和$2$的点,然后把它给splay到根,再对右子树进行区间修改,对他自己单点修改

然后注意特判,如果整棵splay里都没有点权不为$1$或$2$的点,那么直接区间修改

然后怎么记录点权嘞?我们先把所有叶子结点的值*2,那么只有0和2两种值,然后每一个节点只要加上它所有叶子结点的值/2就是这个点的点权了

 //minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<];int C=-;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
sr[++C]=x|,sr[++C]='\n';
}
const int N=,M=;
int fa[M],ch[N][],n1[N],n2[N],tag[N],v[M];
int d[N],q[M],h=,t,ans;
#define ls ch[x][0]
#define rs ch[x][1]
inline bool isrt(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}
inline void pup(int x){
//先右儿子再自己最后左儿子
//因为&是短路运算符,有一个为假就会自动跳出
if(!(n1[x]=n1[rs])&&!(n1[x]=x*(v[x]!=))) n1[x]=n1[ls];
if(!(n2[x]=n2[rs])&&!(n2[x]=x*(v[x]!=))) n2[x]=n2[ls];
}
inline void pdown(int x,int t){
//被区间修改的要么都是1要么都是2,直接反转信息
v[x]^=,swap(n1[x],n2[x]),tag[x]+=t;
}
void all(int x){
if(!isrt(x)) all(fa[x]);
if(tag[x]) pdown(ls,tag[x]),pdown(rs,tag[x]),tag[x]=;
}
void rotate(int x){
int y=fa[x],z=fa[y],d=ch[y][]==x;
if(!isrt(y)) ch[z][ch[z][]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y,pup(y);
}
void splay(int x){
all(x);
for(int y=fa[x],z=fa[y];!isrt(x);y=fa[x],z=fa[y]){
if(!isrt(y))
((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);
rotate(x);
}
pup(x);
}
inline void access(int x){
for(int y=;x;x=fa[y=x])
splay(x),rs=y,pup(x);
}
int main(){
// freopen("testdata.in","r",stdin);
int n=read();
for(int i=;i<=n;++i)
d[fa[read()]=fa[read()]=fa[read()]=i]=;
for(int i=n+;i<=*n+;++i) v[q[++t]=i]=read()<<;
while(h<=t){
int x=q[h++];if(x<=n) pup(x);
v[fa[x]]+=v[x]>>;
if(!(--d[fa[x]])) q[++t]=fa[x];
}
ans=v[]>>;
int q=read();
while(q--){
int x=read(),k=(v[x]^=)-;
access(x=fa[x]),splay(x);
if(~k?n1[x]:n2[x]){
splay(x=(~k?n1[x]:n2[x]));
pdown(rs,k),pup(rs);
v[x]+=k,pup(x);
}
else pdown(x,k),pup(x),ans^=;
print(ans);
}
Ot();
return ;
}

洛谷P4332 [SHOI2014]三叉神经树(LCT)的更多相关文章

  1. 洛谷P4332 &lbrack;SHOI2014&rsqb;三叉神经树(LCT,树剖,二分查找,拓扑排序)

    洛谷题目传送门 你谷无题解于是来补一发 随便百度题解,发现了不少诸如树剖\(log^3\)LCT\(log^2\)的可怕描述...... 于是来想想怎么利用题目的性质,把复杂度降下来. 首先,每个点的 ...

  2. 洛谷4322 SHOI2014 三叉神经树(LCT&plus;思维)

    好久之前做的题了QWQ 现在来补一发博客 一道神仙题啊..qwq 首先,我们可以看出来,我们如果对于每个点维护一个\(val\),表示他的直系儿子中有几个表现为1的. 那么\(val[x]>&g ...

  3. P4332 &lbrack;SHOI2014&rsqb;三叉神经树&lpar;LCT&rpar;

    Luogu4332 LOJ2187 题解 代码-Tea 题意 : 每个点有三个儿子 , 给定叶节点的权值\(0\)或\(1\)且支持修改 , 非叶子节点的权值为当有\(>=2\)个儿子的权值为\ ...

  4. P4332 &lbrack;SHOI2014&rsqb;三叉神经树

    \(\color{#0066ff}{ 题目描述 }\) 计算神经学作为新兴的交叉学科近些年来一直是学术界的热点.一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的 ...

  5. BZOJ 3553&colon; &lbrack;Shoi2014&rsqb;三叉神经树 LCT

    犯傻了,想到了如果是 0->1 的话就找最深的非 1 编号,是 1 -> 0 的话就找最深的非 0 编号. 但是没有想到这个东西可以直接维护. 假设不考虑叶子节点,那么如果当前点的值是 1 ...

  6. 洛谷P3373 &lbrack;模板&rsqb;线段树 2&lpar;区间增减&period;乘 区间求和&rpar;

    To 洛谷.3373 [模板]线段树2 题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输入格 ...

  7. 【BZOJ2830&sol;洛谷3830】随机树(动态规划)

    [BZOJ2830/洛谷3830]随机树(动态规划) 题面 洛谷 题解 先考虑第一问. 第一问的答案显然就是所有情况下所有点的深度的平均数. 考虑新加入的两个点,一定会删去某个叶子,然后新加入两个深度 ...

  8. &lbrack;BZOJ 3553&rsqb;&lbrack;SHOI2014&rsqb;三叉神经树

    传送门(下面也有题面) 题目大意: 一颗有根树,每个非叶子节点都有三个子节点,每个节点的权为0/1. 每个节点的权 取决于其所有子节点中 哪种权出现的次数更多. 有若干次询问,每次询问修改一个叶子节点 ...

  9. 洛谷 P4284 &lbrack;SHOI2014&rsqb;概率充电器 概率与期望&plus;换根DP

    洛谷 P4284 [SHOI2014]概率充电器 概率与期望+换根DP 题目描述 著名的电子产品品牌\(SHOI\) 刚刚发布了引领世界潮流的下一代电子产品-- 概率充电器: "采用全新纳米 ...

随机推荐

  1. phantomjs&plus;selenium实现爬取动态网址

    之前使用 selenium + firefox驱动浏览器来实现爬取动态网址,但是firefox经常更新,更新后时常会导致webdriver启动不来,所以改用phantomjs+selenium来改善一 ...

  2. MEAN实践——LAMP的新时代替代方案(上)

    摘要:90 年代,LAMP 曾风靡一时,然而随着需求的变迁和数据流量的激增,LAMP 已不可避免的走下神坛.近日,在 MongoDB Blog 中,Dana Groce 介绍了一个基于新时代架构的实践 ...

  3. 文件I&sol;O(不带缓冲)之creat函数

    本篇博文内容摘自<UNIX环境高级编程>(第二版),仅作个人学习记录所用.关于本书可参考:http://www.apuebook.com/. 也可调用creat函数创建一个新文件. #in ...

  4. TypeScript设计模式之组合、享元

    看看用TypeScript怎样实现常见的设计模式,顺便复习一下. 学模式最重要的不是记UML,而是知道什么模式可以解决什么样的问题,在做项目时碰到问题可以想到用哪个模式可以解决,UML忘了可以查,思想 ...

  5. shell入门笔记1:执行方式、运行方式、变量、替换

    说明: 本文是关于http://c.biancheng.net/cpp/shell/的相关笔记 shell的两种执行方式 交互式(interactive) 解释执行用户的命令,用户输入一条命令,She ...

  6. ECMAScript6 入门-let与const命令

    块级作用域 1:let命令声明的变量只在let命令所在的代码块有效--简而言之 大括号既是代码块,也就是说存在块级作用域了. { let a =10; var b =1; } a // Referen ...

  7. &lbrack;C&plus;&plus;&rsqb;Qt 如何处理密集型耗时的事情(频繁调用QApplication&colon;&colon;processEvents)

    https://www.cnblogs.com/senior-engineer/p/5598133.html https://www.cnblogs.com/findumars/p/5607683.h ...

  8. eShopOnContainers 看微服务 ②:配置 启动

    一.什么是docker Docker 是一个开源项目,通过把应用程序打包为可移植的.自给自足的容器(可以运行在云端或本地)的方式,实现应用程序的自动化部署. 使用 Docker 的时候,需要创建一个应 ...

  9. iOS基础知识之属性及属性关键字

    iOS属性及属性关键字 一.属性功能:1.给现有的成员变量生成一对setter/getter方法.2.如果没有声明成员变量,自动声明一个_属性名的私有变量(默认的成员变量是受保护的). 二.属性关键字 ...

  10. 第六周PSP&amp&semi;进度条

    团队项目PSP 一.表格:     C类型 C内容 S开始时间 E结束时间 I时间间隔 T净时间(mins) 预计花费时间(mins) 讨论 讨论alpha完成情况并总结 9:40 11:20 17 ...