题目：http://pan.baidu.com/s/1c0uA9Sc

标程：http://pan.baidu.com/s/1dDCj8bv

数据：http://pan.baidu.com/s/1qWNs1Us

Mst

这个题目是用来送分的，思路和我WC讲过的一个题差不多。看链接中的课件里的mst一题。

首先注意到，答案就是最小瓶颈生成树（最大边最小的生成树）上的最大边的期望。

进一步分析可以注意到，考虑一个x，如果<x的边合起来不能使得图联通，<=x的边合起来能够使得图联通，那么这个图的最小瓶颈生成上的最大边就是x。

那么，用WC讲过的同样的方法，我们可以得到一个多项式P(x)，表示<x的边不能使得图联通的概率。

那么注意到，我们只需要对P(x)从0到1求积分就是答案了。为什么呢？因为P(x)也是答案>x的概率，这样相当于一个分部积分。

（这样说可能对于不熟悉微积分的同学来说可能不好理解，不妨考虑离散的情况。比如a有5种取值,0,1,2,3,4，令p[i]为a的取值>i的概率，那么EX[a]=sum p[i]。这里也是一样的道理）

Tree

其实这个题目并不难，题目等价于支持修改点权和寻找整个树的带权重心。

可以考虑使用点分治。注意到如果当前分治点是u，那么显然，我们可以先看看u是不是重心，如果不是，那么重心只可能在u最大的孩子里，这样问题就变成了u的一个子分治的子问题。

当然对于子分治我们还要考虑从u出去整个外面部分的影响，由于树分治最多有logn层，这样的影响也只有logn个，简单的处理就可以了。

Substring

首先题目中有一个关键条件是说叶子的数量不超过20个。

我们不妨对每个叶子都以它为根建一个Trie。

那么注意到整个树的任何一个子串，都是某个Trie上从一个点到它的一个子孙的路径。

那么，我们可以把这20个Trie合并成一个大Trie，然后求这个大Trie的子串数量就可以了（Trie的子串指的是从Trie中一个点到它的一个子孙）。

这可以使用比较经典的后缀自动机或者后缀数组实现。

17 thoughts on “ZJOI 2015 Day 1题解”

前排跪

ORZ

求数据

orz orz orz 陈老师太神了

前排跪

Pingback: 【BZOJ3926】【Zjoi2015】诸神眷顾的幻想乡广义后缀自动机 | 程序员之家

orz orz orz!

This is a really good tip particularly to those
fresh to the blogosphere. Brief but very precise info Appreciate your sharing this one.
A must read article!

Look at my weblog; claires coupon in store, Shirleen,

Howdy I am so happy I found your website, I really
found you by error, while I was researching on Aol for something else, Nonetheless I am here now and would just
like to say cheers for a fantastic post and a all round entertaining blog (I also love the theme/design), I dont have time to
browse it all at the minute but I have bookmarked it and
also added your RSS feeds, so when I have time I will be back to read
a great deal more, Please do keep up the great jo.

my web-site … claire’s coupon code october 2013 – Evonne –

I’m not sure exactly why but this website is loading extremely slow
for me. Is anyone else having this problem or is it a issue on my end?
I’ll check back later and see if the problem still exists.

We’re a bunch of volunteers and opening a brand new scheme in our community.
Your website offered us with helpful information to work on. You have done a formidable activity and our entire group
might be grateful to you.