1、题意:给个树,边的权值=两边的点数差*此边的长度,求所有边的权值和
2、分析:真不想说啥了。。。dfs即可
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define M 2000010 inline int read(){ char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct Edge{ int u, v, w, next; } G[M]; int head[M], tot; int size[M]; LL ans; int n; inline void add(int u, int v, int w){ G[++ tot] = (Edge){u, v, w, head[u]}; head[u] = tot; } inline void dfs(int x, int fa){ size[x] = 1; for(int i = head[x]; i != -1; i = G[i].next) if(G[i].v != fa){ dfs(G[i].v, x); size[x] += size[G[i].v]; ans += (LL)abs(n - size[G[i].v] - size[G[i].v]) * (LL)G[i].w; } } int main(){ n = read(); memset(head, -1, sizeof(head)); for(int i = 1; i < n; i ++){ int u = read(), v = read(), w = read(); add(u, v, w); add(v, u, w); } dfs(1, 0); printf("%lld\n", ans); return 0; }
BZOJ2435——[Noi2011]道路修建的更多相关文章
-
BZOJ2435:[NOI2011]道路修建 (差分)
Description 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1条双向道 ...
-
BZOJ2435 [Noi2011]道路修建 【树形Dp 吧。。】
题目 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1条双向道路. 每条道路的修 ...
-
BZOJ2435 NOI2011道路修建
要多简单有多简单.然而不知道为啥在luogu上过不掉. #include<iostream> #include<cstdio> #include<cmath> #i ...
-
【题解】 bzoj2435: [Noi2011]道路修建 (傻逼题)
bzoj2435,懒得复制,戳我戳我 Solution: 模拟即可(有点傻逼啊 Code: //It is coded by Ning_Mew on 5.13 #include<bits/std ...
-
BZOJ2435: [Noi2011]道路修建
这种水题真是……没一次AC都不好意思见人啊 P.S. LINUX无限栈真是爽炸了… 我爱递归 /**************************************************** ...
-
【DFS】bzoj2435 [Noi2011]道路修建
两遍DFS.第一遍统计以每个点为根的子树大小,第二遍更新答案. #include<cstdio> #include<iostream> using namespace std; ...
-
【BZOJ-2435】道路修建 (树形DP?)DFS
2435: [Noi2011]道路修建 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 3115 Solved: 1002[Submit][Statu ...
-
bzoj 2435: [Noi2011]道路修建 树上 dp
2435: [Noi2011]道路修建 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/pr ...
-
NOI2011道路修建
2435: [Noi2011]道路修建 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1974 Solved: 550[Submit][Status ...
随机推荐
-
常用MySQL图形化管理工具
MySQL的管理维护工具非常多,除了系统自带的命令行管理工具之外,还有许多其他的图形化管理工具,这里我介绍几个经常使用的MySQL图形化管理工具,供大家参考. MySQL是一个非常流行的小型关系型数据 ...
-
Windows下PhpStorm结合WAMP开发Phalcon应用的配置
最近要利用Phalcon框架开发PHP应用,因为以前基本没接触过PHP更没用过PHP框架,结果整环境整IDE配置什么的花了好长时间 学习慕课网上的PHP入门教程安装了WAMP(windows+apac ...
-
CF1153C Serval and Parenthesis Sequence
题目地址:CF1153C Serval and Parenthesis Sequence 思路:贪心 如果有解,那么 \(s_0 = (\) && \(s_{n-1} = )\) &a ...
-
《Redis开发与运维》读书笔记
一.初始Redis 1.Redis特性与优点 速度快.redis所有数据都存放于内存:是用C语言实现,更加贴近硬件:使用了单线程架构,避免了多线程竞争问题 基于键值对的数据结构,支持的数据结构丰富.它 ...
-
windows 解放鼠标快捷键
win+ 调整某个窗口的放大缩小靠边站,最小化 窗口间的切换alt+tablealt (按住)+table(一下)+ 上下左右 alt(一下)+table(一下)相邻切换 alt(按住)+tables ...
-
C# Winfom 中ListBox的简单用法
https://www.cnblogs.com/xielong/p/6744805.html Winform控件ListBox的用法 1.如何添加listBox的值 this.listBox1.Ite ...
-
SliverList , SliverFixedExtentList
SliverList 高度自动, SliverFixedExtentList 高度固定死. CustomScrollView( slivers:[ SliverList( delegate: Sliv ...
-
linux 常用重启
sudo reboot 为最常用重启 Linux centos关机与重启命令详解与实战 Linux centos重启命令: 1.reboot 普通重启 2.shutdown -r now 立刻重启(r ...
-
java.lang.ClassNotFoundException: org.springframework.web.servlet.DispatcherServlet解决
spring配置之后启动报错,如下: java.lang.ClassNotFoundException: org.springframework.web.servlet.DispatcherServl ...
-
magento登陆
magento判断用户登录 Magento 登陆之后返回登录之前的页面 magento 在登陆后一般会自动跳转到 My Account 页面 但是经常会有需求 就是登陆自动跳转到 之前的页面里面 工具 ...