【题目描述】：
    有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。
    每一个点有ci头牛，保证∑ci=N。
    每头牛都可以顺时针走。设一头牛走了d个单位停下了，将耗费d^2的能量。
    请设计一种牛的走法，使得每一个点上都正好有一头牛，且最小化耗费的能量。
【题目解法】：
    我是乱搞的TAT
    我们考虑枚举环的起点，这样所有的奶牛都只能往右边走
    然后考虑一个奶牛，他在i，要走到j，在[i,j]之间还有一个位置k的奶牛没有走过
    显然x^2+y^2<=(x+y)^2，因此我们先i->k，然后换一个奶牛k->j，这样最优
    因此我们从后往前枚举，如果一个点的奶牛数量为1，显然合法跳过，如果>1显然该起点不合法
    如果为0，我们从前面最近的地方拉一条奶牛过来即可，复杂度O(N)
    然后总的复杂度O(N^2)
    题目没有范围。一开始一位这一定是水题，然后就TLE了
    我们考虑事实上对于某个起点开始的序列可能不合法
    考虑前缀和sum[i]>=i对任意i成立合法
    我们将原数组两倍之后枚举起点i，对于[i,i+n-1]中任意一个点j都要满足sum[j]-sum[i-1]>=j-(i-1)
    也就是sum[j]-j>=sum[i-1]-(i-1)，右边和j无关，因此我们求的sum[j]-j的区间最小值即可
    维护一个线段树，判断是否合法，实际上合法的情况很少
    然后就飞快的跑过去了TAT

阅读更多……

【题目描述】：
    给出1~n的一个排列的一个最长上升子序列，求原排列可能的种类数。
【题目解法】：
    一开始交评测姬卖萌，300+ms就给我返回了TLE TAT
    之前做过一道类似的DP套DP的题目，那题我是用f[i]表示以i结尾的LIS长度，然后利用前缀max来获得状态
    这题我们如法炮制，利用前缀和作为状态
    但是由于这题为一个排列，因此我们必须修改状态
    我们用一个3进制表示状态：2表示该位置没有填，0 1分别表示意味着比上一个不为2的位置的LIS前缀和大0 1
    每一次转移我们必定是将一个2变成0或1，因此状态一定变小，我们倒着DP即可
    每次转移，如果枚举的这个数字在给定的LIS中，我们先判断他的前面一个是否加进去，并且判断加入之后以他为结尾的LCS是否为给定的长度，并且最长的LIS是否大于给定的LIS长度，暴力转移即可
    复杂度O(N^2*3^N)
    然后这只是理论复杂度，实际上远远达不到这个上界

阅读更多……

【写在前面】：
    其实没啥好写的，我就是好奇斐波那契数列的性质
    在这篇blog中，前两项不一定为1，我们称之为类斐波那契数列
    证明过程什么的就不写了，直接上结论啦！
【参考】：
    百度百科

http://www.cnblogs.com/grenet/archive/2013/04/30/3051984.html

http://www.matrix67.com/blog/archives/4891

http://blog.csdn.net/acdreamers/article/details/8989772

【斐波那契数列定义】：
    F[1]=1 F[2]=1
    F[i]=F[i-1]+F[i-2] (i>2)
    数列F称为斐波那契数列
【通项公式】：

【斐波那契数列性质】： 
    1.F[1]+F[3]+...+F[2n-1]=F[2n]
    2.F[2]+F[4]+...+F[2n]=F[2n+1]-1
    3.F[1]^2+F[2]^2+...+F[n]^2=F[n]*F[n+1]
    4.F[n-1]*F[n+1]=F[n]^2+(-1)^n
    5.gcd(F[n],F[m])=F[gcd(n,m)]
    6.F[1]+F[2]+...+F[n]=F[n+2]-F[2]
    7.F[n+m]=F[n+1]*F[m]+F[n]*F[m-1]
    8.3*F[n]=F[n-2]+F[n+2]
【类斐波那契数列定义】：
    f[1]=a f[2]=b
    f[i]=f[i-1]+f[i-2] (i>2)
【类斐波那契数列性质】：
    1.f[1]+f[2]+...+f[n]=f[n+2]-f[2]
    2.f[n]=a*F[n-2]+b*F[n-1] (F[n]为斐波那契数列)
    3.f[1]*f[n+m]=f[n+1]*f[m]+f[n]*f[m-1]

【题目描述】：

【题目解法】：
    裸的矩阵乘法，由于n m比较大，我又不知道能不能用femat小定理，所以我们直接硬上十进制快速幂辣
    然后就被卡常数了QwQ
    算了TAT，手动矩阵转移，我们发现3*3里面有一行的值是不会变的，我们可以手动转移其它6个值
    还是TLE？我上Contest Hunter上交了一发，2s+AC？
    大新闻：bzoj没有Contest Hunter快？（大雾弥漫）
    然后将int改成longlong，去掉一堆%P总算是10s+A掉了TAT

阅读更多……

【题目描述】：
    小A和小B又想到了一个新的游戏。
    这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
    最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
    小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
    每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
    小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
【题目解法】：    
    考虑在一个1*n的棋盘上放置K个棋子，相当于有K+1堆石子，石子数可以为0，总的石子个数为n-K，先手后手在偶数堆上做NimK游戏
    考虑所有放置石子的方案，我们将每一堆石子个数+1，然后变成每一堆的石子个数至少为1
    然后使用隔板法，一共有n+1个石子，因此有n个空隙；要隔成K+1堆，因此选择K个空隙。所以全集为C(n,K)
    考虑NimK游戏，先手必败当且仅当石子数所有二进制位每一位上1的个数取模(d+1)都为0
    我们求出先手必败状态即可
    f[i][j]表示二进制前i位放置了j个石子的方案数
    f[i][j]->f[i+1][k*(d+1)*(1<<i)]*C(K/2,k*(d+1))
    然后我们考虑对于一个合法的奇数堆组合f[15][i]，我们还要考虑上偶数的情况
    现在剩下n-K-i个石子，放在K/2+1堆中，每一堆石子可以为0。
    因此我们同样处理，将每一堆都+1，然后变成n-K-i+K/2，拆成K/2份，因此就是C(n-K-i+K/2,K/2)
    时间复杂度O(15*N*K)

阅读更多……

【写在前面】：
    趁着GDKOI还没考，先把这些奇怪的坑填上
    想写博弈论纯属意外，本来在做SDOI的题目，做了一道叫做黑白棋的题目
    然后发现不会，去搜了一发题解，发现是Nim游戏的变种
    然后把这种变种查了一下，有发现了一堆变种TAT，然后就入坑了QwQ
    不管了，既然选择就不能放弃嘛~
【参考】：

http://blog.csdn.net/acm_cxlove/article/details/7854530

    一些国家集训队的论文都已经包含在爱神的blog里面了，就不赘述了
【SG模型】：
    其实解决博弈问题有一类通用方法，就是利用SG函数
    什么是SG函数捏？百度百科的定义是这样滴：
    “对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。”
    也就是说我们把任何的博弈看成是一个图，每一个博弈的局面看成是一个点，然后如果局面A可以转化为局面B，那么就在图上连一条有向边，那么博弈游戏就转化为一张有向无环图，那么就有了上面的定义
    考虑SG函数有啥用捏？百科上的那些P-position和N-position太麻烦了，你可以直接记住结论：sg(x)=0说明局面x先手必败
    本着严谨的态度我还是来证明一发吧：（注意：mex(S)表示集合S中最小没有出现过的自然数）
    对于图中任意结点它的sg值不外乎两种情况：sg(x)=0和sg(x)!=0（额⊙▂⊙好像是废话TAT）
    我们考虑对于sg(x)不为0的点，也不外乎两种情况：后继集合为空或者后继集合中的点sg都不为0
    而对于sg(x)!=0的点，只有一种情况：后继集合中存在一个点sg=0
    以上性质十分显然，就不详细说了，现在我们来证明sg!=0的局面为先手必胜态，sg=0的局面为先手必败态
    1.我们考虑先手面对着一个sg不为0的局面，显然先手可以把这个局面移动一个sg=0的局面，然后后手捏？他只能把局面移动到一个sg!=0的局面，因为sg=0的局面的后继局面都是sg!=0，所以后手很无奈咯QwQ。因此无论怎么样，先手总有后继局面不为空（为空的话sg=0），而后手捏？如果不为空还好，但是毕竟是无环图啊，总有一天会变成空集滴。所以捏，先手必胜！
    2.如果先手面对着一个sg为0的局面，那么相当于先手后手换一下名字，然后就变成了上面的情况，先手必败！
    呼呼～终于证明完了。
    然后我们考虑一个问题，如果这个问题是由多个局面组合而成，那么整个问题的sg等于每个局面的sg的异或和
    为啥博弈游戏回合二进制异或扯上关系捏？其实我也不知道啊TAT，详细证明可以参考张一飞的《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
    从以上我们看出：对于任意的博弈问题都可以用SG函数解决...个鬼啊！
    注意在OI考试中题目是有时间空间限制的，对于有些问题，我们很难在规定的时空限制内推出局面的SG值，因此对于一些特殊的题目，我们需要归纳出特殊的模型从而特殊的解决问题（一口气这么多“特殊”我也真是厉害啊TAT）
【Anti-SG模型】：
    定义：
    1.决策集合为空的决策者胜
    2.其它的规则和普通SG游戏相同
    现在有应该怎么解决呢？我直接给出答案好了
    前提：当某个子问题的sg=0时游戏结束
    1.存在某个子问题的sg>1，且整个问题的sg!=0
    2.所有子问题的sg=1，且整个问题sg=0
【Multi-SG模型】：
    定义：
    1.一个单一游戏的后继可以是多个子游戏
    2.其余的和普通SG游戏相同
    其实捏，我也不太明白这类游戏是什么鬼TAT
    我上网找了一道例题，也不知道是不是这种类型的：
    给出一行N个格子，先手后手轮流话'X'，首先连成3个的人赢
    我们考虑一下对于先手如果碰到X_X或者_XX或者XX_的状态就赢了
    所有我们在对方画了一个X后，这个X左右各两个格子的位置都不能话X，否则对手就赢了
    因此每画一个X，想到于把两边各两个格子去掉，然后转化为两边的子游戏，我们把两边的子游戏SG分别求一下异或起来就是后继局面的SG了。（难道这就是所谓的“一个单一游戏的后继可以是多个子游戏”？）
    SG函数记忆化搜索一下即可
【Every-SG模型】：
    定义：
    1.对于没有结束的单一子游戏，决策者必须分别都进行一次决策
    2.其余与普通SG游戏相同
    有这样一个策略：我们能赢的子游戏要尽量长时间的玩下去，我们必败的子游戏最好尽量早的结束
    因此我们定义step(x)为局面x的最优完成步数，然后我们分情况讨论：
    1.sg(x)=0，显然我们希望x尽早结束：step(x)=min(step(y)+1) y是x的后继局面且sg(y)!=0
    2.sg(x)!=0，显然我们希望x晚点结束：step(x)=max(step(y)+1) y是x的后继局面且sg(y)=0
    3.x为终止状态，step(x)=0
    因此我们得出结论：先手必胜当且仅当单一游戏中最大的step为奇数

Nin游戏是最基础的博弈论问题，下面有几种Nim游戏的变种，我将不再给出详细证明

如果有需要可以自行查找论文

【Nim游戏】：
    什么是Nim游戏呢？我给出一种通俗的定义：有N堆石子，先手后手轮流取，每次从一堆中取出若干个不能不取，取走最后一个的人获胜，问先手是否有必胜策略？
    我们考虑用SG函数解决，定义sg(a1,a2,...,an)表示一个局面，ai为第i堆石子的个数，然而我们发现对于N<=1000000的数据范围我们SG函数无能为力，难道SG函数不是万能的吗？
    显然不是，我们坚信SG函数是万能的，错就错在我们求SG函数的手段。
    其实对于这样一个问题，我们可以将他继续分解，把它变成有1堆石子，他有ai个，询问先手是否有必胜策略。
    对于这样一个游戏，它的sg值就是是石子数，即sg(ai)=ai。这很显然，sg(i)=mex(sg(0),sg(1),...,sg(i-1))=i
    然后我们利用上面的结论，整个游戏的sg值就是每个子问题的sg异或和，也就是说：
    sg(a1,a2,..,an)=sg(a1)^sg(a2)^...^sg(an)=a1^a2^...^an
    至此，这个问题解决了，求出一个局面的sg后，如果为0，那么先手必败，如果sg不为0，那么先手必胜
    我来简单的证明一下：假设sg!=0，那么我们一定可以找到一堆石子，我们拿去若干个，使得sg=0，那么后手面对着一个sg=0的局面，他只能到达一个sg!=0的局面。而终止态的sg=0，所以先手可以永远不可能面对sg!=0，并且使得后手永远是sg=0，因此后手总有一天会输的！
【K-Nim游戏】：
    定义：每次最多只能取K个，问先手是否有必胜策略
    在这种问题中，一堆石子的sg为ai%(k+1)，整个游戏的sg就是石子的sg函数异或和
【S-Nim游戏】：
    定义：每次取得个数只能是给定集合S中的数字，问先手是否有必胜策略
    在这个问题中，只能暴力sg，利用定义mex得到sg，然后异或起来就可以了
【Anti-Nim游戏】：
    定义：每次可以取任意个（不能不去），取最后一个的人输，问先手是否有必胜策略
    先手必胜有以下两种：
    1.所有堆的石子数都为1，且sg=0
    2.不是所有堆的石子数都为1，且sg!=0
【阶梯Nim游戏】：
    定义：一个n阶台阶，每个台阶上有若干石子。每次选择一个台阶上若干石子向下移动一个台阶，将最后一个石子移动到地上的人获胜
    结论：对奇数的台阶上的石子做Nim游戏即可
【NimK游戏】：
    定义：每次从不超过K堆的石子中取任意数量的石子，问先手是否必胜
    结论：将每一堆石子数变成二进制，统计每一位上1的个数即为cnt[i]，将cnt[i]对(K+1)取模，如果全都是0则必败，否则必胜

翻硬币问题也是一个很经典的问题

【翻硬币问题】：
    一般定义：
    1.每次按照一定约数条件翻：如连续的若干枚
    2.每次翻得的硬币最右边一定是从正面翻成反面
    3.无法操作者输
    结论：局面的SG值为各个正面朝上的硬币单一存在是局面的异或和
    我们用0表示反面，用1表示正面
    例如：sg(0011001)=sg(001)^sg(0001)^(0000001)
    以下给出几种不同约束条件下单一游戏sg值（sg(i)表示有i个硬币即左边i-1个反面最后一个正面的sg值）
    由于sg(0)=0，如无特殊情况，我们忽略0
    1.每次翻一个硬币：sg=1
    2.每次翻任意一个或两个硬币：sg值为编号
    3.每次连续K个：sg值从1开始为000…01 000…01，其中一小段0的个数为K-1
    4.每次翻了一个x后，必须在x-1 x-2 x-3任选一个翻动：sg从1开始为12301230...
    5.每次翻动两个，距离为1或2或3：sg从1开始12301230...
    6.每次翻动1或2或3个，当x的二进制有偶数个1时sg(x)=2*x+1，有奇数个1是sg(x)=2*x。注意这是特殊情况，sg(0)=1
    7.每次翻动连续任意个至少一个，sg(x)为x中2的最大次幂，如sg(16)=16 sg(12)=4
【二维翻硬币问题】：
    约定坐标范围[0..n-1,0..m-1]
    一般定义：
    1.每次翻一个连通快，且所有点都要在最右下方那个点的左上方
    2.每次翻得的硬币最右下那个一定是从正面翻成反面
    3.无法操作者输
    结论：局面的SG值为各个正面朝上的硬币单一存在是局面的异或和
    给出sg：
    sd(i,j)=lowbit(i+j+1) (i=0||j=0)
    sg(i,j)=2^(i+j) (i,j!=0)

还有一部分是删边问题，分为三种：

1.树删边

2.仙人掌删边

3.无向图删边

【树上删边游戏】：
    定义：
    1.每次删去一条边，将不与根节点连通的部分删去
    2.不能这么做的人输
    结论：
    1.叶子节点的sg为0
    2.非叶子结点的sg为子节点的sg+1后的异或和
    我们只要证明只有一个儿子结点成立，那么多个儿子结点变成了Nim游戏，全部加1后异或和就是答案
    我们利用书柜证明只有一个儿子结点成立：
    1.1个2显然成立
    2.假设K成立，那么证明K+1成立
      我们去掉一条边，一定是剩余的点<=K
      假设去掉根节点和唯一儿子的边，显然后继局面sg=0
      假设去掉唯一儿子子树中的边，那么在那个子树中sg=P，由于<=K是成立，那么sg就是P+1
      因此当前局面的后继局面sg值为0,1,2,..,sg+1
      得证！
【仙人掌删边游戏】：
    1.对于奇数的环，sg=1
    2.对于偶数的环，sg=0
    因此我们将偶数的环删去，将奇数环变成长度为1的短链
    然后变成一棵树辣！
【无向图删边】：
    有一个著名的结论：
    1.将原图的偶数环变成一个点
    2.将原图的奇数环变成一条边+一个点
    所有与原来环相连的边全部连到点上
    然后变成一棵树辣！并且树的sg与无相图的sg相同

呼呼～终于完结了

其实大部分都是摘抄爱神blog的内容TAT

不过自己也算是领略的不少新的姿势

希望对今后的解题有所帮助

完结撒花！

【题目描述】：
     现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。
     当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。
     某K国的军事基地是这样子的：地面上两排大天井共n1个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为1,3,5…和2,4,6…并且最大的编号为n1。
      虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看。。。
      我们有很牛X的特种部队，只需要派出一支特种部队到K国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的K国基地内的空腔。
      当然，你的基地离K国基地不会太近，周边的地图将会给你，表示为n个检查点和m条连接这些点的道路，其中点1到点n1就是K国基地的出入口，点n是你的部队的出发点。对每条道路，有不同的通行时间t和安全系数s。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。
      一支特种部队从你的基地出发，通过某条路径，到达某个K国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个K国基地。
      快点完成这个任务，在K国的叫兽宣布你是K国人之前。
【题目解法】：
    《几个算法拼凑起来系列》
    瞄了一眼题解，貌似用了分数规划TAT
    出题人你真萌，既然要分数规划干嘛不把边权发大一点，你给个t<=10摆明暴力上啦
    我们用dis[i][j]表示到达i点安全系数为j时最小的时间，1<=i<=n 1<=j<=n*10
    spfa一发即可
    然后处理处dist[i]表示到达i点最小的比值
    对于奇数i，连边(s,i,dist[i])
    对于偶数i，连边(i,t,dist[i])
    对于某一个空腔u，它的两个出入口x y，连边(x,u,INF) (u,v,INF)
    然后最小割即可
    脑补了一下分数规划sigma(t[i])/sigma(s[i])=aim最小
    假设当前找到的最优解为now，令边权为t[i]-s[i]*now，然后跑最短路dist
    如果dist<0说明sigma(t[i])-sigma(s[i])*now<0 => sigma(t[i])/sigma(s[i])<now，说明存在比now更有的解
    二分或者迭代即可

阅读更多……

【题目描述】：
    给定序列A，序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若干项，使得4的最长上升子序列长度减少至少1，且付出的代价之和最小，并输出方案。
    如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。
【题目解法】：
    首先第一问是裸的最小割
    我们用f[i]表示以i结尾的最长上升子序列长度
    然后将每个点i拆成i和i'
    对于f[i]=1的点，连边(s,i,INF)
    对于f[i]=MaxF点的，连边(i',t,INF)
    然后对于每个点i，连边(i,i',b[i])
    对于两个点i,j满足a[j]<a[i]且f[j]+1=f[i]，连边(j',i,INF)
    最小割就是答案，这样就有30pt
    考虑构造字典序最小的方案，我们按照C排序，然后贪心的加入
    考虑什么情况下某条边(i,i')一定在某个最小割中？
    很简单，两个条件：
    1.(i,i')满流（显然）
    2.我们强制割开i i'，如果最小割不变，那么(i,i')一定在某个最小割中
    如何强制割开某条边呢？我们连边(s,i,INF) (i',t,INF)，这样就可以强制将i留在s割，i'留在t割，自然这条边就割开了
    但是这样判断每次都要跑最大流，会TLE...
    我们考虑如果i->i'之间如果存在增广路，那么一定有s->i->i'->t的增广路，此时最小割会增大
    如果i->i'之间没有增广路，那么最小割不会增大。
    因此我们O(N)判断一下i->i'是否存在增广路即可
    然后考虑删去(i,i')对图的影响，我们显然需要把(i,i')对原图的影响恢复回去
    也就是说把流过(i,i')的流退回去即可
    那么我们Sap(t,i') Sap(i,s)，然后把(i,i')删去即可
    然后TLE辣TAT
    不虚，我会卡常数...
    QwQ...慢慢都是泪啊
    我们考虑推流是一定退了b[i]，因此Sap时判断最大流是否已经等于b[i]了
    然后就过了TAT

阅读更多……

【题目描述】：
    几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号(“”’)，可以匹配0个及以上的任意字符：另一个是问号(“？”)，可以匹配恰好一个任意字符。
    现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。
    字符串长度不超过100000
    1<=n<=100
    通配符个数不超过10
【题目描述】：
    《感觉复杂度不对系列》
    我们考虑一个一个的去匹配
    考虑动态规划，我们用f[i][j]表示模板串前i个和匹配串前j的是否可以匹配，根据对应字符匹配即可
    然后这样做的复杂度是O(|S|^2)，显然会MLE+TLE
    我们考虑对于不包含通配符的模板串，我们直接KMP一下，然后DP转移即可
    即：如果模板串在匹配串中成功匹配的起点为i，长度为len，那么f[next][i+len-1]|=f[cur][i]
    然后我们考虑对于'?',显然f[next][i]|=f[cur][i-1]
    对于'*'，我们找到第一个f[cur][i]为true的，然后将f[next][i...n]全部变成true
    考虑这样做的复杂度，这样做相当于把不含通配符的一段当成一个字符来处理，由于最多只有10个通配符，那么压缩后的字符串长度不超过20
    因此复杂度就是O(|S|*20)，|S|=100000
    恩恩，看起来很靠谱滴样子，等等外面还有个N=100
    时间复杂度O(N*|S|*20) TAT
    不管了，写一发，然后A了不科学啊TAT

阅读更多……

【题目描述】：
    给定一个n个点的树，每个点的编号从1至n，问这个树有多少不同的连通子树，和这个树有相同的重心。
其中n个点的树指的是n个点的最小连通图，显然n个点的树有n-1条边，去掉这n-1条边中的任何一条，原图都不再联通，任意两个点之间由唯一一条路径相连。
    对于一个树，树的重心定义为：删掉某点i后，若剩余k个连通分量，那么定义d(i)为这些连通分量中点的个数的最大值，所谓重心，就是使得d(i)最小的点i。
    基于以上定义，一个树的重心可能会有一个或者两个，题中所要求的联通子树，其重心编号和个数必须和原树的完全一样。
    找出给定的树中有多少联通的子树和这个树有相同的重心。
【题目描述】：
    根据重心的性质我们知道：如果重心的所有子树s1 s2 s3 ... sk，假设s1为最大
    1.若2*s1<n，那么重心唯一
    2.若2*s1=n，那么重心有两个且相邻
    所以我们求出所有重心后，分情况讨论
    1.如果重心是唯一的，我们把重心提根
    现在我们需要选取子树使得重心唯一且为根节点
    我们枚举一下选取子树大小，设为Size，那么需要根节点所有子树的大小s满足2*s1<Size，且s1+...+sk=Size-1
    我们令：
    f[i][j]表示从以i为根的子树选取j个结点的连通子树个数
    g[i][j]表示当前的子树前i个子节点中选取j个结点的连通子树
    g[i][j]=sigma(g[i-1][k]*f[son[i]][j-k])
    f[i][j]=g[SonNum][j]
    然后对于根节点，我们特殊处理一下，即在处理g数组的时候使得任何一棵子树大小满足2*s1<Size即可
    2.如果重心有两个，那么他们一定相邻，我们将两个重心之间边切去，那么变成两棵树
    我们需要从两个树中选取大小相同的两颗子树（注意一定要连着重心）
    我们依然令：
    f[i][j]表示从以i为根的子树选取j个结点的连通子树个数
    g[i][j]表示当前的子树前i个子节点中选取j个结点的连通子树
    g[i][j]=sigma(g[i-1][k]*g[son[i]][j-k])
    f[i][j]=g[SonNum][j]
    然后枚举两边子树大小乘起来即可
    时间复杂度O(N^3*Q)

阅读更多……