关键词：
典型树上dp，直接暴力算会超时，小心呀
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define maxn 100010
using namespace std;
typedef long long ll;
struct Node
int p;
ll len;
Node(int a, ll b) :p(a), len(b)
;
vector<Node>G[maxn];
void insert(int be, int en,ll len)
G[be].push_back(Node(en, len));
int n, m;
ll sum = 0;
ll ran[maxn];
ll ans[maxn];
ll list[maxn];
int dfs1(int x, int fa)
ll k = 0;
for (int i = 0; i < G[x].size(); i++)
int p = G[x][i].p;
ll ln = G[x][i].len;
if (p == fa) continue;
dfs1(p, x);
k = ran[p];
ans[x] += (ans[p] + ran[p] * ln);
ran[x] += ran[p];
return 0;
int dfs(int x, int fa)
for (int i = 0; i < G[x].size(); i++)
int p = G[x][i].p;
ll ln = G[x][i].len;
if (p == fa) continue;
ans[p] += ans[x] - (ans[p] + ran[p] * ln) + (sum - ran[p])*ln;
dfs(p, x);
return 0;
int main()
scanf("%d", &n);
m = n - 1;
for (int i = 1; i <= n; i++)
scanf("%lld", &list[i]);
sum += list[i];
ran[i] = list[i];
int be, en;
ll len;
for (int i = 0; i < m; i++)
scanf("%d%d%lld", &be, &en, &len);
insert(be, en, len);
insert(en, be, len);
dfs1(1, -1);
dfs(1, -1);
ll cns = 10000000000000000;
for (int i = 1; i <= n; i++)
cns = min(cns, ans[i]);
printf("%lld
", cns);
return 0;
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然， 查看详情
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…
典型树上dp，直接暴力算会超时，小心呀 #include<cstring>#include<iostream>#include<algorithm>#include<cstdio>#include<vector>#definemaxn100010usingnamespacestd;typedeflonglongll;structNode intp; lllen; Node(inta,llb):p(a),len(b);vec... 查看详情
p2986[usaco10mar]伟大的奶牛聚集（思维，dp）(代码片段)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方... 查看详情
p2986[usaco10mar]伟大的奶牛聚集(代码片段)
题意：给一棵n个点的边+点权树，求带权重? 思路：其实这题和之前那个Sta有点像，我们同样只需要预处理出一个f[u]代表以u为集合点的方便程度，那么我们就可以O（1）的转移了假设v是u的儿子，f[v]=f[u]-(siz[v]*len)+(n-siz[v])... 查看详情
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)
一道比较经典的题（蒟蒻的我没有一次切掉）…… 首先这道题要优化的原因就是数据范围，要是O(n2) “ 显然 ”会超时。。。 那么我们很不情愿不得已不开心地最终被迫考虑一下优化（说实话好多算法都... 查看详情
[usaco10mar]伟大的奶牛聚集
[USACO10MAR]伟大的奶牛聚集Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情
洛谷p2986[usaco10mar]greatcowgat…(树形dp+容斥原理)
P2986[USACO10MAR]伟大的奶牛聚集GreatCowGat…题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace. 查看详情
bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)
【题解】 很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。 我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。 显然选择它的儿子... 查看详情
[usaco10mar]伟大的奶牛聚集-树形dp(代码片段)
每个点有重数，求到所有点距离最小的点就是魔改的重心了#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1000005;vector<pair<int,int>>g[N];intsiz[N],f[N],vis[N],sum[N],c[N],n,m,t1,t2,t3,tot;voiddfs1(intp)vis[p]=1;siz[p]=c[p];for(inti=0;i<... 查看详情
bzoj1703[usaco2007mar]rankingthecows奶牛排名*
bzoj1703[Usaco2007Mar]RankingtheCows奶牛排名题意：n头奶牛，知道n对奶牛之间的产奶量大小，问想知道所有奶牛产奶量大小顺序至少还需知道几对。n≤1000。题解：每个大小关系看为一条有向边，对每头奶牛进行dfs，求每头奶牛可以到... 查看详情
bzoj3375[usaco2004mar]paranoidcows发疯的奶牛*
bzoj3375[Usaco2004Mar]ParanoidCows发疯的奶牛题意：依次给出n只奶牛的产奶时间段，求最大的k使得前k只奶牛不存在一个时间段被另一个时间段完全覆盖的情况。n≤100000。题解：设当前在处理第i只奶牛，前i-1只奶牛都合法。那么如果... 查看详情
[bzoj]1657:[usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:858 Solved:603[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverystraigh 查看详情
[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛
1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1312 Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情
[bzoj1657][usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:863 Solved:607[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverys 查看详情
[usaco2010mar]gather奶牛大集会
[Usaco2010Mar]gather奶牛大集会题目Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条... 查看详情
[bzoj]1657:[usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 867 Solved: 610[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsa 查看详情
洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper
P3052[USACO12MAR]摩天大楼里的奶牛CowsinaSkyscraper题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingt 查看详情
bzoj3401[usaco2009mar]lookup仰望*
bzoj3401[Usaco2009Mar]LookUp仰望题意：约翰的N头奶牛站成一排，奶牛i的身高是Hi。对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j。求出每只奶牛离她最近的仰望对象。n≤100000.题解：用一个单调栈维护即可... 查看详情