关键词：
1827: [Usaco2010 Mar]gather 奶牛大集会
Description
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。 考虑一个由五个农场组成的国家，分别由长度各异的道路连接起来。在所有农场中，3号和4号没有奶牛居住。
第一行：一个整数N * 第二到N+1行：第i+1行有一个整数C_i * 第N+2行到2*N行，第i+N+1行为3个整数：A_i,B_i和L_i。
Output
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
Sample Output
15
题解
考虑在点\(x\)处的答案为\(ans\)，总奶牛数为\(tot\)，i为根子树总奶牛数为\(size_i\),对于\(x\)的一个儿子\(y\)的答案为\(ans^'\),\(y\)到\(x\)边权为\(w\)
有
\[ans^' = ans - size_i \times w + (tot - size_i) * w\]
化简得
\[ans^' = ans + (tot - 2 \times size_i) * w\]
即\(tot - 2 \times size_i < 0\)时t比x优
从根跑下来找到最优点然后以它为起点dfs/bfs一遍就行了。。
bzoj1827:[usaco2010mar]gather奶牛大集会
【算法】树型DP【题解】两遍DFS，第一次得到所有节点子树的路径和，第二次给出除了该子树外其它部分的路径和，时时计算答案。longlong！！！#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#definelllonglongu... 查看详情
bzoj1827[usaco2010mar]gather奶牛大集会（树形dp）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1827 【题目大意】 给出一棵有点权和边权的树， 请确定一个点，使得每个点到这个点的距离乘上该点乘积的总和最小。 【题解】 定1为根，我们先计... 查看详情
bzoj1827[usaco2010mar]gather奶牛大集会
题目描述 Description Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情
bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)
【题解】 很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。 我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。 显然选择它的儿子... 查看详情
p1827[usaco3.4]美国血统americanheritage树的遍历(代码片段)
题目 代码#include<iostream>#include<cstdio>#include<string>#include<cstring>usingnamespacestd;charin[100];charpre[100];intlen=0;voidpostorder(charin[],charpre[],intlen) 查看详情
嘴巴题6bzoj3450joyoi1952easy
TimeLimit:10SecMemoryLimit:128MBSubmit:936Solved:698[Submit][Status][Discuss]Description某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(我们来简化一下这个游戏的规则有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，... 查看详情
bzoj千题计划156：bzoj1571:[usaco2009open]滑雪课ski
http://www.lydsy.com/JudgeOnline/problem.php?id=1571 DP不一定全部全状态转移贪心的舍去一些不合法的反而更容易转移在一定能力范围内，肯定滑雪所需时间越少越好当课程的结束时间和能力值改变相同时，肯定课程越晚开始越好预处理... 查看详情
bzoj1589[usaco2008dec]trickortreatonthefarm采集糖果
题目链接本来想做强连通分量的题的然而这个题太水了。。。随便搞搞就过了一个连通块里有且仅有一个环，从所有入度为0的点出发找出环，记录答案然后只有一个圈但没有“把”的再来考虑1#include<algorithm>2#include<... 查看详情
bzoj1619/p2919[usaco08nov]守护农场guardingthefarm(代码片段)
P2919[USACO08NOV]守护农场GuardingtheFarm相似题：P3456[POI2007]GRZ-RidgesandValleys每次bfs海拔相同的块，根据与周围的块的大小关系判断是否是山丘。1#include<iostream>2#include<cstdio>3#include<cstring>4#include<queue> 查看详情
bzoj1915:[usaco2010open]奶牛的跳格子游戏
权限题，没有传送门。这很显然是一道DP题，刚看完题目可能会比较懵逼。这道题如果不要求回去，那么就是一道很裸的DP题。但是本题要求回去而且回去的格子的前一个格必须是之前经过的。先不考虑回去的路程，对于一段长... 查看详情
bzoj千题计划187：bzoj1770:[usaco2009nov]lights燈（高斯消元解异或方程组+枚举自由元）
http://www.lydsy.com/JudgeOnline/problem.php?id=1770 a[i][j]表示i对j有影响高斯消元解异或方程组然后dfs枚举自由元确定最优解 #include<cstdio>#include<algorithm>usingnamespacestd;#defineN36intn;boola[N][N];bool 查看详情
[bzoj3378][usaco2004open]moofest狂欢节_树状数组
MooFest狂欢节bzoj-3378Usaco-2004Open题目大意：给定一个n个数的a序列，每两个数之间有一个距离，两个点之间的权值为$max(a[i],a[j])*dis(i,j)$。注释：$1lenle2cdot10^4$。想法：裙子说了，这种$max$和$min$的题通常要枚举这个$max$和$min$到底是... 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情
bzoj1615/p2903[usaco08mar]麻烦的干草打包机theloathesomehaybaler(代码片段)
P2903[USACO08MAR]麻烦的干草打包机TheLoathesomeHayBaler细节题。$O(n^2)$的$bfs$可过。1#include<iostream>2#include<cstdio>3#include<cstdlib>4#include<cstring>5#include<cctype>6#include< 查看详情
●bzoj1233[usaco2009open]干草堆tower
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=1233 留坑。以后再来看看。 （绝望，无奈，丧心。。。） （这个题的证明真的很诡异啊，看得我稀里糊涂的。） 查看详情
树的直径bzoj3363[usaco2004feb]cowmarathon奶牛马拉松(代码片段)
3363:[Usaco2004Feb]CowMarathon奶牛马拉松Description?最近美国过度肥胖非常普遍，农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松．马拉松路线要尽量长，所以，告诉你农场的地图（该地图的描述与上题一致），请帮助约翰寻找两... 查看详情
bzoj5277:[usaco2018open]outofsorts(代码片段)
被tkj大爷艹爆了5555整套模拟赛都是神仙思路题那么这题题解 还有一个神仙做法，zory巨神在考场上找规律AC，自己都不会证。。我证明了一下(然而这货还是不认可自己的做法)按照分割点的思路，我们for循环一次，每次找到比... 查看详情
bzoj1643/p2666[usaco2007oct]bessie'ssecretpasture贝茜的秘密草坪(代码片段)
[Usaco2007Oct]Bessie‘sSecretPasture贝茜的秘密草坪简单的dfs题枚举前3个完全平方数，判断最后一个是不是完全平方数，统计合法方案数即可。（zz选手竟把数据看成<=1e9）1#include<iostream>2#include<cstdio>3#include<cstring>4#include... 查看详情