P2052 [NOI2011]道路修建
2019-10-29 16:01:15来源:博客园 阅读 ()
P2052 [NOI2011]道路修建
题目:
P2052 [NOI2011]道路修建
解析:
维护一下每个子树的\(size\),这条边的贡献就是\((n-size[v]-size[v])*w\),\(v\)是这条边所到达的点,\(w\)是边权
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int n, m, num, ans;
int head[N], size[N];
struct node {
int v, nx, w;
} e[N];
inline void add(int u, int v, int w) {
e[++num] = (node) {v, head[u], w}, head[u] = num;
}
void dfs(int u, int fa) {
size[u] = 1;
for (int i = head[u]; ~i; i = e[i].nx) {
int v = e[i].v;
if (v == fa) continue;
dfs(v, u);
ans += abs(n - 2 * size) * e[i].w;
size[u] += size[v];
}
}
signed main() {
ios::sync_with_stdio(false);
memset(head, -1, sizeof head);
cin >> n;
for (int i = 1, x, y, z; i < n; ++i)
cin >> x >> y >> z, add(x, y, z), add(y, x, z);
dfs(1, 0);
cout << ans;
}
原文链接:https://www.cnblogs.com/lykkk/p/11759565.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Luogu P1070 道路游戏 2018-09-29
- BZOJ3624: [Apio2008]免费道路(最小生成树) 2018-09-19
- BZOJ2339: [HNOI2011]卡农(dp 容斥) 2018-09-01
- 洛谷P2052 [NOI2011]道路修建(树形DP) 2018-07-06
- BZOJ2434: [Noi2011]阿狸的打字机(AC自动机 树状数组) 2018-07-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash