题不算难,但还是有一点坑的
求一条边一侧的结点数量显然可以 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 呢(笑)。
氵完睡觉。
标签:结点,int,修建,dfs,P2052,NOI2011,ans,size From: https://www.cnblogs.com/Iictiw/p/17413472.html