P2052 [NOI2011] 道路修建
题不算难，但还是有一点坑的
求一条边一侧的结点数量显然可以 dfs 求出来，另一侧结点数就是 \(n-size_i\) ，其中 \(size_i\) 是结点 \(i\) 的子树大小。
long long ans,size[N];
inline void dfs(int p,int fa){
size[p]=1;
for(auto i:v[p]){
if(i.to==fa)continue;
dfs(i.to,p);
size[p]+=size[i.to];
ans+=i.val*abs(size[i.to]-(n-size[i.to]));
}
}
值得一提的是在乘法时就有可能爆 int ，不知道有多少人像这样 100 -> 40 呢(笑)。
氵完睡觉。