题目链接

BZOJ 3696

题目大意

介于这是一道权限题，先讲一下题意
有一棵根节点编号为1的数，给出每一个节点的父亲。
对于点对(x,y)，令他们的LCA为k，定义这对点对的A值为dis[x][k])^dis[y][k]，dis即为两点间的最短距离(边数)，
最后求出对于x=(1…n)，A值为x的点对的数量。
点数1e5，且题目保证最大的深度为500

NOIP2018游记

前言

今天说要写游记，机房的大佬们问我为什么现在才写，估计是因为以前也没写过不知道怎么写，而且今天正式才成绩出来，算是尘埃落定了吧。

前言

首先讲一下线性基是什么东西，线性基是一个集合，你在原集合中找到一个子集，子集中的数xor起来一定能在线性基中找一个对应子集的xor和与其相等。
比如说，{x,y}和{x,x^y} 就满足这么样一个关系。

前言

笛卡尔树，与Treap类似，每个节点拥有两个值，key值和val值。key值是这个节点本身的大小值，在一颗treap中满足二叉查找树的性质，而val值则是一个随机值，学过treap的同学都知道，这个val值是拿来使得树的层高是期望log的，val值满足堆的性质，这里以小根堆为例讲解（当然大根堆不会有任何问题）。

前言

先贴一道模板题 Luogu 2495
题意，给你一棵n个点的有边权树，有m次询问，每次询问k个点，要删除一些边使得这k个点均不与1号点联通。
数据范围：$2\le n\le250000,m\ge1,\sum k_i\le500000,1\le ki\le n-1$；

前言

矩阵乘法，常常被用作递推式的优化，如果把一个递推式一步的递推转换成乘上一个矩阵，那么由于矩阵乘法有结合律，所以我们就可以快速幂啦，起到优化的效果。而递推式出现最多的地方当然就是dp了，所以今天想简单的总结一下矩阵乘法优化dp。

前言

停更好久了，刚好我们老师讲了莫比乌斯反演，那我就来开数论这个天坑吧。

莫比乌斯反演

比如说我们现在有一个函数$f(n)=\sum_{d|n}g(d)$
假设f非常容易求得，但是g很难求，那么我们是不是可以通过f来求g呢
$g(n)=\sum_{d|n}f(\frac{n}{d})*\mu(d)$
然后$mu(d)$这个东西就是莫比乌斯函数，所以这个变换也叫莫比乌斯变换

搞了三四天终于搭出了自己的博客，OI不一定能够成功，但至少留下这个博客可以怀念