BZOJ2435——[Noi2011]道路修建

时间:2023-02-27 07:32:01

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]道路修建的更多相关文章

  1. BZOJ2435&colon;&lbrack;NOI2011&rsqb;道路修建 &lpar;差分&rpar;

    Description 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1条双向道 ...

  2. BZOJ2435 &lbrack;Noi2011&rsqb;道路修建 【树形Dp 吧。。】

    题目 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1条双向道路. 每条道路的修 ...

  3. BZOJ2435 NOI2011道路修建

    要多简单有多简单.然而不知道为啥在luogu上过不掉. #include<iostream> #include<cstdio> #include<cmath> #i ...

  4. 【题解】 bzoj2435&colon; &lbrack;Noi2011&rsqb;道路修建 (傻逼题)

    bzoj2435,懒得复制,戳我戳我 Solution: 模拟即可(有点傻逼啊 Code: //It is coded by Ning_Mew on 5.13 #include<bits/std ...

  5. BZOJ2435&colon; &lbrack;Noi2011&rsqb;道路修建

    这种水题真是……没一次AC都不好意思见人啊 P.S. LINUX无限栈真是爽炸了… 我爱递归 /**************************************************** ...

  6. 【DFS】bzoj2435 &lbrack;Noi2011&rsqb;道路修建

    两遍DFS.第一遍统计以每个点为根的子树大小,第二遍更新答案. #include<cstdio> #include<iostream> using namespace std; ...

  7. 【BZOJ-2435】道路修建 (树形DP?)DFS

    2435: [Noi2011]道路修建 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 3115  Solved: 1002[Submit][Statu ...

  8. bzoj 2435&colon; &lbrack;Noi2011&rsqb;道路修建 树上 dp

    2435: [Noi2011]道路修建 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/pr ...

  9. NOI2011道路修建

    2435: [Noi2011]道路修建 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1974  Solved: 550[Submit][Status ...

随机推荐

  1. 常用MySQL图形化管理工具

    MySQL的管理维护工具非常多,除了系统自带的命令行管理工具之外,还有许多其他的图形化管理工具,这里我介绍几个经常使用的MySQL图形化管理工具,供大家参考. MySQL是一个非常流行的小型关系型数据 ...

  2. Windows下PhpStorm结合WAMP开发Phalcon应用的配置

    最近要利用Phalcon框架开发PHP应用,因为以前基本没接触过PHP更没用过PHP框架,结果整环境整IDE配置什么的花了好长时间 学习慕课网上的PHP入门教程安装了WAMP(windows+apac ...

  3. CF1153C Serval and Parenthesis Sequence

    题目地址:CF1153C Serval and Parenthesis Sequence 思路:贪心 如果有解,那么 \(s_0 = (\) && \(s_{n-1} = )\) &a ...

  4. 《Redis开发与运维》读书笔记

    一.初始Redis 1.Redis特性与优点 速度快.redis所有数据都存放于内存:是用C语言实现,更加贴近硬件:使用了单线程架构,避免了多线程竞争问题 基于键值对的数据结构,支持的数据结构丰富.它 ...

  5. windows 解放鼠标快捷键

    win+ 调整某个窗口的放大缩小靠边站,最小化 窗口间的切换alt+tablealt (按住)+table(一下)+ 上下左右 alt(一下)+table(一下)相邻切换 alt(按住)+tables ...

  6. C&num; Winfom 中ListBox的简单用法

    https://www.cnblogs.com/xielong/p/6744805.html Winform控件ListBox的用法 1.如何添加listBox的值 this.listBox1.Ite ...

  7. SliverList &comma; SliverFixedExtentList

    SliverList 高度自动, SliverFixedExtentList 高度固定死. CustomScrollView( slivers:[ SliverList( delegate: Sliv ...

  8. linux 常用重启

    sudo reboot 为最常用重启 Linux centos关机与重启命令详解与实战 Linux centos重启命令: 1.reboot 普通重启 2.shutdown -r now 立刻重启(r ...

  9. java&period;lang&period;ClassNotFoundException&colon; org&period;springframework&period;web&period;servlet&period;DispatcherServlet解决

    spring配置之后启动报错,如下: java.lang.ClassNotFoundException: org.springframework.web.servlet.DispatcherServl ...

  10. magento登陆

    magento判断用户登录 Magento 登陆之后返回登录之前的页面 magento 在登陆后一般会自动跳转到 My Account 页面 但是经常会有需求 就是登陆自动跳转到 之前的页面里面 工具 ...