构造
这种贡献在边上的题的套路就是按边考虑。对于一条边，它的贡献一定不超过它两端子树的大小的较小值。开一个脑洞就会发现我们确实可以构造出这样一个方案。以重心为根，使每一条路径都经过重心即可。由于每一个子树的大小不超过n/2，所以这是一定能构造出来的。
#include<cstdio>#include<algorithm>#define N 100005using namespace std;namespace runzhe2000{ typedef long long ll; int n, last[N], ecnt, siz[N]; ll ans; struct edge{int next, to, v;}e[N<<1]; void addedge(int a, int b, int c) { e[++ecnt] = (edge){last[a], b ,c}; last[a] = ecnt; } void dfs(int x, int f) { siz[x] = 1; for(int i = last[x]; i; i = e[i].next) { int y = e[i].to; if(y != f) { dfs(y, x); siz[x] += siz[y]; ans += (ll)e[i].v * min(siz[y], n - siz[y]); } } } void main() { scanf("%d",&n); for(int i = 1, a, b, c; i < n; i++) { scanf("%d%d%d",&a,&b,&c); addedge(a, b, c); addedge(b, a, c); } dfs(1,0); PRintf("%lld/n",ans); }}int main(){ runzhe2000::main();}新闻热点
疑难解答
