路终会有尽头，但视野总能看到更远的地方。

题目大意

    在一棵树或环套树上等概率选择起点行走，每次等概率地前往一个还没去过的相邻点，求路径的期望长度。

题目大意

题目大意

    一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。
    今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。
    为了使舞会更有神秘感，主办方把面具分为$k(k\ge3)$类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第$i$类面具的人才能看到戴第$i+1$类面具的人的编号，戴第$k$类面具的人能看到戴第$1$类面具的人的编号。
    参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。
    栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第$2$号面具的人看到了第$5$号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。
    由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。
    由于主办方已经声明了$k\ge3$，所以你必须将这条信息也考虑进去。

题目大意

    给出一棵树，每次在树上增加/减少权值，维护其带权重心。

题目大意

    Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的右买不到。展览中总共有$N$种珠宝，每种珠宝都只有一个，对于第$i$种珠宝，它的售价为$C_i$万元，对Miranda的吸引力为$V_i$。Miranda总共可以从银行中取出$K$万元，现在她想知道，假如她最终带了$i$万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？
    $1\le N\le1000000,1\le K\le50000,1\le C_i\le300,0\le V_i\le10^9$

题目大意

    Miranda生活的城市有$N$个小镇，一开始小镇间没有任何道路连接。随着经济发现，小镇之间陆续建起了一些双向的道路但是由于经济不太发达，在建设过程中，会保证对于任意两个小镇，最多有一条路径能互相到达。有的时候Miranda会从某个小镇开始进行徒步旅行，每次出发前，她都想选择一个她能到达的最远的小镇作为终点，并且她在行走过程中是不会走回头路的，为了估算这次旅行的时间，她会需要你告诉她这次旅行的时间会是多少呢？可以假设通过每条道路都需要单位时间，并且 Miranda 不会在小镇停留。
    强制在线。

题目大意

    给出一个有向图，指定一些起点与终点，询问从指定起点与终点的所有路径中选出最少多少路径可以覆盖原图。

题目大意

    小Y最近学得了最短路算法，一直想找个机会好好练习一下。话虽这么说，OJ上最短路的题目都被他刷光了。正巧他的好朋友小A正在研究一类奇怪的图，他也想凑上去求下它的最短路。
    小A研究的图可以这么看：在一个二维平面上有任意点$(x,y)$（$0\le x\le N,0\le y\le M$,且$x,y$均为整数），且$(x,y)$向$(x-1,y)$（必须满足$1\le x$）和$(x,y-1)$（必须满足$1\le y$）连一条边权为$0$的双向边。
    每个点都有一个非负点权，不妨设$(x,y)$的权值为$F[x][y]$，则有：
    1.$x=0$或$y=0$：$F[x][y]=1$；
    2.其他情况：$F[x][y]=F[x-1][y]+F[x][y-1]$。
    现在，小Y想知道$(0,0)$到$(N,M)$的最短路，即使得经过的点的权值之和最小。为了炫耀自己学过最短路算法，他决定和你进行一场比赛，看谁的程序跑得快。然则小Y没有学过高精度算法，所以他希望输出答案时只输出答案模$1000000007$后的值。

题目大意

    轮换$g:(q_1\,\,q_2\,\,q_3\cdots q_k)$是一个从$\lbrace1,2,\ldots,n\rbrace$到$\lbrace1,2,\ldots,n\rbrace$的一一映射，它将$q_1$映射为$q_2$，$q_2$映射为$q_3$，$\ldots$，$q_k$映射为$q_1$，而在$q_1,q_2,\ldots,q_k$中没有出现的整数映射到自身。即：$g(q_1)=q_2,g(q_2)=q_3,\ldots,g(q_k)=q_1$，而对于在$q_1,q_2,\ldots,q_k$中没有出现的$x$，$g(x)=x$。定义将轮换$g$应用到一个$\lbrace1,2,\ldots,n\rbrace$的排列$(p_1,p_2,\ldots,p_n)$上的结果为：$g(p_1,p_2,\ldots,p_n)=(g(p_1),g(p_2),\ldots,g(p_n))$例如，对排列$(3,1,5,4,2)$应用轮换$(1\,\,3\,\,4)$进行变换后可得到排列$(4,3,5,1,2)$。给定$\lbrace1,2,\ldots,n\rbrace$的一个排列$(p_1,p_2,\ldots,p_n)$和一些轮换，请给出一种使用尽量 少的轮换次数将该排列变换为$(1,2,\ldots,n)$的方法。每个轮换可以使用多次。

题目大意

    物理学家栋栋最近在研究一个能量场。在这个能量场中有$n$个粒子,每个粒子都有两个属性:质量$m$和结合系数$c$。
    栋栋发现,在这个能量场中,每个粒子都有两极,$N$极和$S$极。两个粒子相遇时,符合“同极相斥,异极相吸”的原则,只能是一个粒子的$N$极和另一个粒子的$S$极连接到一起。当质量为$m_a$,结合系数为$c_a$的粒子$a$的$N$极与另一个质量为$m_b$,结合系数为$c_b$的粒子$b$的$S$极直接连接时,可以产生大小为

$$m_am_b(c_a-c_b)$$

    的结合能量。
    请解决以下两个问题:
    1.在能量场的$n$个粒子中哪两个粒子直接连接的能量最大。
    2.栋栋发明了一种方法,能选择其中的任意$k$个粒子$p_1,p_2,\ldots,p_k$,将$p_i$的$N$极与$p_i+1$的$S$极连接$(1\le i\lt k)$,$p_k$的$N$极与$p_1$的$S$极连接, 即连接能一个环,其中$p_1,p_2,\ldots,p_k$两两不同,$k$可以在$1$至$n$中任意取值。由于栋栋的技术有限,连接的时候产生负能量的那些连接在环中必须是连续的。如使用栋栋的这种方法连接,选择哪些粒子可以得到最大的能量。