xiaoMa
"Bye Bye Baby Blue"

FollowTheWind


FollowTheWind
搜索什么...

P1501,ZJOI-2012(LCT)

P1501 [国家集训队]Tree II 题目描述 一棵 $N$个点的树,每个点的初始权值为 $1$。对于这棵树有 $q$ 个操作,每个操作为以下四种操作之一: + u v c:将 $u$到 $v$ 的路径上的点的权值都加上自然数 $c$;- u1 v1 u2 …

   58   2020-05-23   0 去围观

LCT(动态树)总结

最近学了学$LCT$,简单讲下。 一【理论知识】 -$Link-Cut-Tree$(简称 LCT) 是解决动态树类问题一种数据结构 -$Preferred Child$:重儿子,重儿子与父亲节点在同一棵 $Splay$ 中,一个节点最多只能有一个重儿子 -$Preferred Edge$:重边,连接父亲节点和重…

   110   2020-04-27   0 去围观

一些树链剖分的题目(1)

手残党的噩梦😏 SPOJ-QTREE 这道题把边权转化成点权,单点修改就行 #include<bits/stdc++.h> using namespace std ; inline int read() { register int x = 0 ; register int f = 1 ; register char c = getchar() ; for( ; ! isdigit(c) ; c = getchar…

   85   2020-04-18   0 去围观

POJ-2104(可持久化线段树)

查询区间第$K$大,朴素的算法是将区间排序,并输出第$K$个数字,意味着复杂度将是$O(nmlog n)$。

   122   2020-04-04   1 去围观

splay维护二叉搜索树

简介 $splay$是一种二叉查找树,它通过不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找树的性质,并且保持平衡而不至于退化为链,它由 Daniel Sleator 和 Robert Tarjan 发明。 https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91 操作 $g…

   124   2020-03-19   0 去围观

P3384,HAOI2015(树链剖分)

树剖代码量还是很大的,如果没有压行的话,200+是肯定要的😁。感觉我的手速跟不上了。。。 P3348 题目描述 如题,已知一棵包含 $N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作 $1$: 格式: $1$ $x$ $y$ $z$…

   154   2020-03-14   0 去围观

密码保护:3.12

这篇文章受密码保护,输入密码才能看哦

   120   2020-03-12   要查看留言请输入您的密码。 去围观

树链剖分(LOJ-139)

给定一棵  个节点的树,初始时该树的根为  号节点,每个节点有一个给定的权值。下面依次进行  个操作,操作分为如下五种类型: 换根:将一个指定的节点设置为树的新根。修改路径权值:给定两个节点,将这两个节点间路径上的所有节点…

   120   2020-03-10   0 去围观

树上差分(POJ-3417)

http://poj.org/problem?id=3417 一颗n−1n−1条主要边的树,然后增加了mm条附加边. 我们只能删除一条主要边,一条附加边,一种边叫做主要边,一种边叫做附加边. 要求删除两条边后,这棵树不再是连通的. 对于每一条连接x,y节点的(x,y),其实我们都可以认为这条边,…

   89   2020-03-08   0 去围观

LCA树上倍增(HDU-2586)

勇气小镇是一个有着n个房屋的小镇,为什么把它叫做勇气小镇呢,这个故事就要从勇气小镇成立的那天说起了, 修建小镇的时候,为了让小镇有特色,镇长特地只修了n-1条路,并且规定说,所有在勇气小镇的村民,每一次出门必须规划好路线 ,路线必须满足在到达终点之前绝对不…

   122   2020-02-29   0 去围观
加载更多