HDU4871 Shortest-path tree(点分治)

题目题面大意是给你一个图,要你构建出一棵最短路树,再询问经过k个点的最长路径长度以及最长路径条数。思路点分治。点分治的思路是这样的:对于一个点$x$而言,对答案有影响的路径要么经过点$x$要么不经过,利用这点进行分治。点分治首先要找出一个重心。重心是指以该点为根所有的子树中sz最大的最小。然后,对于每一棵子树进行处理,统计答案(点分治题目不同的地方就在这,其它都是板子)之后再递归进重心的子树中处理

- 阅读全文 -

BZOJ4399 魔法少女LJJ

题目在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味;小猴在枝头悠来荡去,好不自在;各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果;鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ还是太naive,一天,SHY带着自己心爱

- 阅读全文 -

BZOJ4771 七彩树

题目给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点。每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i]。如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面,你将面临m个问题。每个问题包含两个整数x和d,表示询问x子树里且depth不超过de

- 阅读全文 -

可持久化Trie树整理

前言Trie树(字典树)是一种比较简单的数据结构,一般人yy一下也能想到。具体而言,路径用$pa[maxnode][sigmasize]$来表示。如果对于英文字母来说,就是$pa[M][26]$,这种情况下整棵树就是一棵不满的26叉树。使用时往往也需要在节点上同时维护信息。插入代码void Insert(char *s,int v){ int u=0,len=strlen(s);

- 阅读全文 -

typecho博客搭建指南

前言在wordpress日趋臃肿的今天,小而美的typecho成了不少人的选择。笔者原来也是wordpress的死忠粉,认为wordpress是搭建博客的最佳选择。其优点如下:文档社区支持广泛,基本上遇到的坑很容易百度出答案。插件·主题系统完备,傻瓜式安装功能强大。但是,知道有一天,笔者的markdown插件挂了之后,看到它复杂的仪表盘,我终于意识到,这些看似酷炫的功能其实都是多余的。作为一个博客

- 阅读全文 -