题目传送门(BZOJ)
>原文链接<

题解 :

​ 由于是一棵树,所以一条边的两边分别有$siz_a, n-siz_a$个点,取差的绝对值就是$|(2\times siz -n)|$。

我们只要做一个基础的树形DP,维护个$siz$就可以了。

由于$N$太大 会爆栈,BFS一遍,然后从队列尾往前更新,这样一定是每个儿子都给父亲产生贡献之后,父亲才会对其父亲贡献。

NOI的人口普查题。

代码 :

#include <map>#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 1100000;struct Edge { int to, val; Edge *next;}*h[N], e[N<<1];inline int Abs(int x) {return x > 0 ? x : -x; }inline void Add_Edge(int u, int v, int w) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}int q[N], l, r;int siz[N], fa[N];int main() { int n = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(), w = rd(); Add_Edge(u, v, w); Add_Edge(v, u, w); } q[++r] = 1; while(l < r) { int u = q[++l]; siz[u] = 1; rev(i, u) if(i->to != fa[u]) { fa[i->to] = u; q[++r] = i->to; } } for(int i = n; i >= 1; i -- ) { siz[fa[q[i]]] += siz[q[i]]; } long long ans = 0; for(int p = 1; p <= n; p ++ ) { rev(i, p) if(i->to != fa[p]) { ans += (long long)Abs(2*siz[i->to]-n)*i->val; } } printf("%lld\n", ans);}