高精，你妹

generic void真难写

同样是KM，为什么我的常数那么大......?时间都快赶上费用流了

建模好头疼.......勉强看懂了一些

回复 @luo : (logm)^2

动态维护树的直径即可，(注意这不是一个树而是森林), 用每棵树的第一个插入点代表这棵树，预处理每棵树的倍增$LCA$数组，则对树中任意两点的距离的询问可以在$O(logn)$的时间内求得，然后把整个森林重建一遍-----设新加入的点为$k$ 当前树的直径端点为$i$和$j$(初始的$i,j$为根结点)，如果$dis(i,k)>dis(i,j)$那么把直径的端点$j$换成$k$,如果$dis(j,k)>dis(i,j)$那么把直径的端点$i$换成$k$，最后得到的就是树的真正直径.

作一波死赶紧跑......

回复 @BillAlen :
故意的......

回复 @Hzoi_hzoier :
有道题目相似难度更高的题，题目编号2084

30分算法：三维DP？(我反正没想过)
(70)80分算法：
我们不妨把三角变换反过来考虑，不难发现，每次将最小的边改为另外两条边之和减一可以刚好"卡着"三角形两边之和大于第三边的性质，使边权增长最快，因而次数最少。不停迭代，一旦最大的边超过X，那么说明这条边也可以改为X，原题答案就是迭代次数+2(加上把非最大的两条边修改的代价)，那么求解反问题只要分别迭代n-2次得到结果R,迭代n-3次得到结果L，处理一下区间边界即可.
100分算法：
进一步考虑，我们用递推关系来取代迭代关系,即构造递推式
$f_n=f_{n-1}+f_{n-2}-1,(f(1)=y,f(2)=y)$
用矩阵快速幂加速即可

设状态$f(n,t)$为已经进行了t轮且得分为n的游戏方案数，则可以动态规划:
$f(0,0)=1 \\$
$f(n,t)=\sum_{}^{n-k<=x<=n+k} {f(x,t-1)}$
第二维可以用滚动数组优化，转移可以用前缀和优化,由于如果每次得分都达到了-k或者k，总得分上限为$kt$,所以空间复杂度为$O(kt)$,时间复杂度为$O(kt^2)$
设$g(n)=f(n,T)$.$delta=b-a$则如果小A想要战胜小B，得分必须严格大于$delta$,所以我们枚举小A小B的得分，则$ans=\sum_{i}^{-kt<=i<=kt}\sum_{j}^{i-j>delta} {g(i)g(j)}$。
如果预处理$sum(i)=\sum_{i}^{-kt<=i<=kt}g(i)$(也是一个前缀和),则优化为$ans=\sum_{i}^{-kt<=i<=kt}g(i)*sum(i-delta-1)$。
至于转移时出现的负数平移坐标轴即可.

评测插件有问题

我们画图可以发现，如果两个线段相交，则每个线段的两个端点(在圆周上)所对应的劣弧极角区间一定相交,我们计算出这些极角区间，离散化，然后求出有多少对区间相交即可(需要使用线段树/树状数组/平衡树维护),时间复杂度为$\Large O(n\log_2n)$
连立方程,
$\Large ax+by+c=0$
$\Large x^2+y^2=r^2$
得
$\Large x=\frac {-ac\pm \sqrt {(ac)^2+(b^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$
$\Large y=\frac {-bc\pm \sqrt {(bc)^2+(a^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$
然而，一些极角区间可能跨过了0度线,我们不妨称之为智障区间，比如[300,30],我们把这些区间记两次数，以[300,390]计算一次，[-60,30]计算一次，可以保证这两次智障区间和非智障区间相交的对只会被计算一次，然而智障区间和智障区间相交的对被计算了两次，再对所有的智障区间计算一次并减掉即可

回复 @stdafx.h :
有时间我会加

这个保证有解是肯定的，因为我找了一些非常大的数然后随机一堆数取模，所以-1骗不了分。
不是质数的情况就要分解质因数取所有质数的指数的最高项即可（因为$x$ $mod$ $a$ $= c$,$x$ $mod$ $b$ $=$ $c$,则$x$ $mod$ $lcm(a,b) = c$,$lcm$为最小公倍数）而$(2^1,2^5,...... 2^x)$最小公倍数肯定是$2^{max(x)}$，所以我们取新的$P_i$为$2^{max(x)}$即可，然后让使得取得最高项的$A_i$ $mod$ 新的$P_i$作为新的$A_i$,这样的话所有的$P_i$必定互质，构造出新的方程后就按一般互质的情况计算即可
例如下面一组数据：
10
40 39
60 19
14 1
95 39
9 7
85 59
87 55
88 63
96 31
5 4
我们进行转换后得
32 31 //2^5 from 96 31
9 7 //3^2 from 9 7
5 4 //5^1 from 5 4
7 1 //7^1 from 14 1
11 8//11^1 from 88 63(63 mod 11 =8)
17 8//17^1 from 85 59(59 mod 17=8)
19 1//19^1 from 95 39(39 mod 19 =1)
29 26//29^1 from 87 55(55 mod 29=26)

题解有三种做法，一种是$O(n \log^2 n+q)$,一种是$O(n +q\log^2 n)$,一种是$O(n+q)$,

解方程
$ f(x)=0 $
则可以选一个初始值$x_{0}$不断进行迭代
$ x_{n+1}=x_{n}-\frac{f(x)}{f'(x)}\ $
牛顿迭代法，维基百科上的比较详细

回复 @sherc :
孤立的生物不算食物链.....

这题把不吃也不被吃的生物算上食物链20分，否则满分
死于生物没有学好，也不能全怪出题人........