关键词:
一、题目:
二、思路:
这道题怎么说呢?只能说有点意思,让我第一次见识了LCT怎么应用。
首先一个非常明显的性质,就是比如我现在修改了某个叶子结点,记为 \\(leaf\\),那么因此而状态发生改变的点一定是从 \\(leaf\\) 向上的连续区间。所以我们自然而然能想到两种数据结构,一种是树链剖分,另一种就是LCT,因为这两种都可以较好地维护树链的信息。
这题用LCT怎么做呢?难点就在于找出每次的连续区间的终点在哪?当然,由于连续区间的性质,我们立刻就能想到二分答案。时间复杂度 \\(O(n\\log^2 n)\\)。
其实,我们还可以通过维护一些信息来降低一下时间复杂度。具体来说,我们每次打通 \\(leaf\\) 到根的路径,即 \\(\\mathbbaccess(leaf)\\)。这样一来,\\(leaf\\) 到根的所有节点就都在一棵 Splay 中了。我们在这棵 Splay 的每个节点中维护两个信息:\\(id[x,1]\\) 和 \\(id[x,2]\\),分别代表Splay中 \\(x\\) 子树的、原树中最深的、\\(sum\\) 不为 \\(1\\) 或 \\(2\\) 的节点编号。
具体怎么维护呢?请配合注释看代码。
三、代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define FILEIN(s) freopen(s".in", "r", stdin);
#define FILEOUT(s) freopen(s".out", "w", stdout)
#define mem(s, v) memset(s, v, sizeof s)
inline int read(void)
int x = 0, f = 1; char ch = getchar();
while (ch < \'0\' || ch > \'9\') if (ch == \'-\') f = -1; ch = getchar();
while (ch >= \'0\' && ch <= \'9\') x = x * 10 + ch - \'0\'; ch = getchar();
return f * x;
const int maxn = 500005 * 3;
int n, m, son[maxn][2], id[maxn][3], fa[maxn], add[maxn], val[maxn], sum[maxn], tot;
int head[maxn];
struct Edge
int y, next;
Edge()
Edge(int _y, int _next) : y(_y), next(_next)
e[maxn << 1];
inline void connect(int x, int y)
e[++ tot] = Edge(y, head[x]);
head[x] = tot;
inline void update(int o) // 由于Splay结点的中序遍历代表原树的一条从上到下的路径,因此我们必须先看右儿子,再看它自己,最后看它的左儿子。
id[o][1] = id[son[o][1]][1];
id[o][2] = id[son[o][1]][2];
if (!id[o][1])
if (sum[o] != 1) id[o][1] = o;
else id[o][1] = id[son[o][0]][1];
if (!id[o][2])
if (sum[o] != 2) id[o][2] = o;
else id[o][2] = id[son[o][0]][2];
inline void change(int o, int x)
sum[o] += x; val[o] = sum[o] > 1;
swap(id[o][1], id[o][2]); // 修改操作一定只对sum值全部为1或2的区间进行,因此我们只需交换id即可。
add[o] += x;
inline void pushdown(int o)
if (add[o])
if (son[o][0]) change(son[o][0], add[o]);
if (son[o][1]) change(son[o][1], add[o]);
add[o] = 0;
inline bool isroot(int x)
return son[fa[x]][0] != x && son[fa[x]][1] != x;
inline int get(int x) return son[fa[x]][1] == x;
inline void rotate(int x)
int y = fa[x], z = fa[y], k = get(x);
pushdown(y); pushdown(x);
if (!isroot(y)) son[z][son[z][1] == y] = x;
son[y][k] = son[x][k ^ 1]; fa[son[y][k]] = y; fa[y] = x;
son[x][k ^ 1] = y; fa[x] = z;
update(y); update(x);
void correct(int x)
if (!isroot(x)) correct(fa[x]);
pushdown(x);
inline void splay(int x)
correct(x);
for (int f = fa[x]; !isroot(x); rotate(x), f = fa[x])
if (!isroot(f))
rotate(get(x) == get(f) ? f : x);
inline void access(int x)
int z = x;
for (int y = 0; x; y = x, x = fa[x])
splay(x);
son[x][1] = y;
update(x);
splay(z);
void dfs(int x, int fa)
sum[x] = 0;
for (int i = head[x], y; i; i = e[i].next)
y = e[i].y;
if (y == fa) continue;
dfs(y, x);
sum[x] += val[y];
if (x <= n) val[x] = sum[x] > 1;
int main()
n = read();
int x;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= 3; ++ j)
x = read(); fa[x] = i;
connect(x, fa[x]); connect(fa[x], x);
for (int i = n + 1; i <= n * 3 + 1; ++ i) val[i] = read();
dfs(1, 0);
int ans = val[1];
m = read();
while (m --)
int leaf = read(), x = fa[leaf];
int addtag = val[leaf] ? -1 : 1;
access(x);
int w = id[x][val[leaf] ? 2 : 1];
if (w)
splay(w);
change(son[w][1], addtag);
sum[w] += addtag; val[w] = sum[w] > 1; update(w); // 由于w的儿子的id发生了变化,注意要update一下,当然换成splay(w)也是可以的。
else ans ^= 1, change(x, addtag); // 特殊判断w不存在的情况。
val[leaf] ^= 1;
printf("%d\\n", ans);
return 0;
bzoj2830&洛谷3830:[shoi2012]随机树——题解(代码片段)
https://www.luogu.org/problemnew/show/P3830#sub <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考:https://www.cnblogs.com/GuessYCB/p/846249 查看详情
洛谷3833shoi2012魔法树
【题解】 树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情
[shoi2014]三叉神经树(代码片段)
Description:计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI的神经组织因为其和近日发现的化合物SHTSC的密切联系引起了人们的极大关注。SHOI组织由若干个SHOI细胞构成,SHOI细胞之间形成严密的树形结构... 查看详情
洛谷3830[shoi2012]随机树概率dp(代码片段)
题目输入格式输入仅有一行,包含两个正整数q,n,分别表示问题编号以及叶结点的个数。输出格式输出仅有一行,包含一个实数d,四舍五入精确到小数点后6位。如果q=1,则d表示叶结点平均深度的数学期望值;如果q=2,则d表示... 查看详情
shoi2014三叉神经树(代码片段)
传送门一道非常好的LCT/树剖题。但是像我这样的菜鸡想不到什么有效做法……首先我们可以很容易发现,一次如果要在链上连续修改那么肯定是从底向上的一端连续区间。如果我们把每个节点的输入值作为其权值,那么会被连... 查看详情
bzoj-3553三叉神经树树链剖分
3553:[Shoi2014]三叉神经树TimeLimit: 160Sec MemoryLimit: 256MBSubmit: 347 Solved: 112[Submit][Status][Discuss]Description计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI的神经组织因为 查看详情
p3830[shoi2012]随机树题解(代码片段)
P3830随机树坑题,别人的题解我看了一个下午没一个看得懂的,我还是太弱了。题目链接 P3830 [SHOI2012]随机树 题目描述输入输出格式输入格式: 输入仅有一行,包含两个正整数q,n,分别表示问题编号以及叶结点的... 查看详情
bzoj4869:[shoi2017]相逢是问候——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=4869题面复制于洛谷:https://www.luogu.org/problemnew/show/P3747#sub 参考洛谷的前两篇(也是仅有的两篇)题解。首先我们要知道一个公式:这又被叫做扩展欧拉定理,证明我们并不关心。有了扩展... 查看详情
●洛谷p3233[hnoi2014]世界树
题链:https://www.luogu.org/problemnew/show/P3233题解:虚树,dp,倍增。首先对于每个询问,要把虚树建出来,这一步就从略了。这里着重分享一下如何求答案。比如,我们建出来如下一颗虚树,给出的关键点是那些黑点点们,红点点是... 查看详情
[shoi2014]概率充电器(代码片段)
...概率大题我果然是每做出来……然后我找到了一篇极棒的题解,小学生都能看懂(大佬就是大佬啊):题解P4284【[SHOI2014]概率充电器】,第二次dp的状态方程真的很妙啊。刚开始我总按照套路想设\(dp[u]\)表示\(u\)的子树的期望,... 查看详情
题解sdoi2014旅行
洛谷P3313大概是一道树链剖分的裸题。可以看出如果不是查询相同宗教的这一点,就和普通的树链剖分毫无两样了。所以针对每一个宗教都单独开一棵线段树,变成单点修改+区间查询。只不过宗教数目很多,空间消耗太大所以只... 查看详情
bzoj4868:[shoi2017]期末考试——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=4868题目复制于洛谷:https://www.luogu.org/problemnew/show/P3745#sub有n位同学,每位同学都参加了全部的m门课程的期末考试,都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所有课程的... 查看详情
●洛谷p1291[shoi2002]百事世界杯之旅
题链:https://www.luogu.org/recordnew/show/5861351题解:dp,期望 定义dp[i]表示还剩下i个盖子没收集时,期望还需要多少次才能手机完。 初始值:dp[0]=0 显然对于一个状态,我们随机得到一个盖子,有两种可能: 1.得到了曾经没有的盖子... 查看详情
题解shoi2001化工厂装箱员
————传送:洛谷P2530这道题目还是挺简单的,状态也容易想到。数据范围非常的小,所以即便是很多维度,复杂度也完全可以接受。定义状态:dp[i][a][b][c]为手上的货物拿到第i个时三种物品分别有a,b,c个所用的最少次数。状... 查看详情
洛谷3740[haoi2014]贴海报
【题解】 线段覆盖问题。线段树或者并查集都可以。不离散化居然能过? #include<cstdio>#include<algorithm>#defineN10000010#definergregisterusingnamespacestd;intn,m,ans,l[N],r[N],fa[N];inlineintread() intk=0,f=1;charc=getch 查看详情
洛谷p1047校门外的树题解
摘要:此题是一个模拟题,但需要注意的一点就是它的树是从数轴的0开始,所以我们也要从0开始,这样才能实现代码。代码:#include<iostream>usingnamespacestd;ints[100000];intmain()intl,m,x,y,d=0;cin>>l>>m;for(inti=0;i<=l;i++)s[i]=1;fo... 查看详情
洛谷3384:模板树链剖分——题解(代码片段)
https://www.luogu.org/problemnew/show/P3384如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:操作1:格式:1xyz表示将树从x到y结点最短路径上所有节点的值都加上z操作2:格式:2xy表示求树... 查看详情
p2726[shoi2005]树的双中心题解(代码片段)
...度:(O(n^2)).期望得分:(0)~(100pts).(出题人没给部分分,洛谷评测机跑得快)算法二显然,枚举断边无法优化,那我们考虑优化取重心。下面我们要引出一些树链剖分的知识。一个节点(i),它所有儿子(uinson_v)中,(s 查看详情