文档章节

【bzoj2435】道路修建

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:58
字数 380
阅读 6
收藏 0

今天真是愉♂快的一天……
QAQQQQQQQ

大背景:我想学主席树


想学主席树,有人说你得先学可持久化


然后就去学可持久化
我找到WJMZBMR,他说:“就凭你也敢看我课件???”
然后我就去找fhq,fhq亲切友好的与我交谈了半天,然后他说想学这个先去学LCT


然后我就跑去学LCT
我找到了DQS
DQS说:“你还不会链剖你学个篮子”


然后我就去学链剖
结果fhq说:“你等等,我给你个水题……”
我回头他就给我这个题……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAXN = 1000000 + 5;
struct edge
{
    int f,t,v;
}l[MAXN << 1];
int n,m;
int first[MAXN],next[MAXN << 1],tot;
int deep[MAXN],sz[MAXN];
bool use[MAXN];
void init()
{
    memset(first,0xfff,sizeof(first));
    memset(deep,0,sizeof(deep));
    memset(use,0,sizeof(use));
    memset(sz,0,sizeof(sz));
    tot = 0;
    return;
}
void build(int f,int t,int v)
{
    l[++tot] = (edge){f,t,v};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
void dfs(int x,int f)
{
    deep[x] = deep[f] + 1;
    use[x] = true;
    sz[x] = 1;
    for(int i = first[x];i != -1;i = next[i])
    {
        int v = l[i].t;
        if(use[v])
            continue;
        dfs(v,x);
        sz[x] += sz[v];
    }
    return;
}
LL solve()
{
    dfs(1,0);
    LL ans = 0;
    for(int i = 1;i <= tot;i += 2)
    {
        int u = l[i].f,v = l[i].t;
        if(deep[u] > deep[v])
            swap(u,v);
        ans += (LL)((LL)l[i].v * abs((LL)sz[v] - (LL)(n - sz[v])));
    }
    return ans;
}
int f,t,v;
int main()
{
    init();
    scanf("%d",&n);
    for(int i = 1;i < n;i ++)
    {
        scanf("%d %d %d",&f,&t,&v);
        build(f,t,v);
        build(t,f,v);
    }
    printf("%lld\n",solve());
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
noip2018 D1T3 赛道修建

题目描述 C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 mm 条赛道。 C 城一共有 nn 个路口,这些路口编号为 1,2,…,n1,2,…,n,有 n-1n−1 条适合于修建赛道的双向通行的道路,每...

phuaker
02/28
0
0
hdu-1979-继续畅通工程

原文链接:hdu-1979-继续畅通工程 原文: 继续畅通工程 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 26600 Accepted Submiss......

Big_laoshu
2017/11/20
0
0
hdu-1874-畅通工程续

原文链接: hdu-1874-畅通工程续 原文: 畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 58577 Accepted Submission(......

Big_laoshu
2017/11/23
0
0
HDU 3394 Railway 【点双联通】

传送门 // 有一个公园有n个景点,公园的管理员准备修建m条道路,并且安排一些形成回路的参观路线。如果一条道路被多条道路公用,那么这条路是冲突的;如果一条道路没在任何一个回路内,那么这...

Anxdada
2018/02/24
0
0
SDUT-3362 数据结构实验之图论六:村村通公路

数据结构实验之图论六:村村通公路 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 当前农村公路建设正如火如荼的展开,某乡镇政府决定实现村村通公路,工程师现有各个村落之...

wzy_2017
2017/06/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

饿了么交付中心语言栈转型总结

前言: 本文介绍了饿了么交付中心由python语言栈转换到java语言栈大致过程,一来是对前段时间的工作做下总结,另外也是想通过此次总结为其他应用服务转型提供些借鉴。写的不好,欢迎板砖。 背...

一肥仔
26分钟前
4
0
移植linux4.14内核到4412开发板

最近法师收到了很多留言,其中有一部分问法师什么时候更新,还有一大部分问法师我是买迅为的IMX6UL精英版好呢还是买4412精英版好呢,因为我们这俩个都不贵。法师的建议的是入手4412!为什么呢...

书白
30分钟前
7
0
提高GMAT语法能力方法解析,掌握技巧高分不是梦

GMAT考试对考生语法能力的要求涉及各部分的题目,熟练掌握语法知识对于考生获得高分有巨大的帮助。因此,学好GMAT语法,显得非常重要。下面小编就介绍一些提高GMAT语法能力的方法技巧。 做题...

bole6
34分钟前
6
0
100天搞定机器学习|day54 聚类系列:层次聚类原理及案例

几张GIF理解K-均值聚类原理 k均值聚类数学推导与python实现 前文说了k均值聚类,他是基于中心的聚类方法,通过迭代将样本分到k个类中,使每个样本与其所属类的中心或均值最近。 今天我们看一...

机器学习算法与Python实战
36分钟前
5
0
创龙TI KeyStone C66x多核定点/浮点DSP TMS320C665x底板B2B连接器、电源接口和拔码开关

TL665x-EasyEVM是广州创龙基于SOM-TL665x核心板研发的一款TI C66x多核定点/浮点高性能DSP开发板,采用核心板+底板方式,底板尺寸为200mm*106.65mm,采用4*50pin和1*80pin B2B工业级连接器,稳...

Tronlong创龙
38分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部