动态树分治......

gcd a,b 不要反了QAQ 反了a,b只能拿20

113楼，肯定不会再有人盖楼了嘿嘿嘿 [] [] [] [] [] [] []

约翰留下了 N 只奶牛呆在家里，自顾自地去干活了，这是非常失策的。他还在的时候，奶牛像往常一样悠闲地在牧场里吃草。可是当他回来的时候，他看到了一幕惨剧：他的奶牛跑进了他的花园，正在啃食他精心培育的花朵！约翰要立即采取行动，挨个把它们全部关回牛棚。约翰牵走第 i 头奶牛需要 Ti 分钟，因为要算来回时间，所以他实际需要2 · Ti 分钟。第 i 头奶牛如果还在花园里逍遥，每分钟会啃食 Di 朵鲜花。但只要约翰抓住了它，开始牵走它的那刻开始，就没法吃花了。请帮助约翰写一个程序来决定押送奶牛的顺序，使得花朵损失的数量最小。

有n头牛在糟蹋庄稼。把第i头牛牵回家需要ti分钟。第i头牛每分钟会摧毁di的庄稼。每次只能牵一头牛走。问怎么牵使损失最少。
思路：
考虑a,b两牛。先牵a牛和b牛的损失分别为。2*d[b]*t[a]，2*d[a]*t[b]。设先牵a更优。2*d[b]*t[a]<2*d[a]*t[b].
所以根据优先级排序然后依次牵就是最优的选择。

1493==642

农民约翰去砍柴左N（2≤N≤100000）牛吃的草，像往常一样。当他回来的时候，他发现他的恐惧，牛的集群在他的花园里吃他美丽的花。为了减少后续伤害，FJ决定立即采取行动和运输每头牛回到自己的谷仓。
我是在每头奶牛，Ti分钟位置（1≤钛≤2000000）远离自己的谷仓。此外，在等待运输，她破坏了DI（1≤迪≤花每分钟100）。不管他如何努力，FJ一次只能回到谷仓运输一头奶牛。移动的牛我对它的谷仓需要2×Ti分钟（TI去TI返回）。FJ在花片开始，运牛的谷仓，然后走回花，以没有多余的时间去下一头奶牛，需要运输。
写一个程序来确定顺序，FJ应该拿起牛因此总花朵数破坏最小化。输入
1号线：一个单一的整数n
线路2：N + 1：每行包含两个整数Ti和迪，描述一个牛的特点
输出
1号线：一个整数，是被破坏的花的最小数量

SPFA

千分留念

积分：1006
提交：125 / 414

话说这题dp真的不好想= =
然后把b[i][k]打成b[i][j]，这个脑残错误调了两节课= =

我们画图可以发现，如果两个线段相交，则每个线段的两个端点(在圆周上)所对应的劣弧极角区间一定相交,我们计算出这些极角区间，离散化，然后求出有多少对区间相交即可(需要使用线段树/树状数组/平衡树维护),时间复杂度为$\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]计算一次，可以保证这两次智障区间和非智障区间相交的对只会被计算一次，然而智障区间和智障区间相交的对被计算了两次，再对所有的智障区间计算一次并减掉即可

DFS+剪枝

这个可以完全隐式遍历trie（rank1），也可以半隐式遍历（不存儿子全部存在的节点）

回复 @fmj : 666666

搞基排序真慢= =
O(4*N)事件与O(2*N)空间干不过O(N*lgN)QAQ

速度快的一比

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

没有spj啊.. 一个树可能有好几个重心