文档章节

Codevs 联合权值

机智的帝江
 机智的帝江
发布于 2016/10/30 09:55
字数 297
阅读 1
收藏 1

点击就送屠龙宝刀

题目描述 Description
这里写图片描述
输入描述 Input Description
这里写图片描述
输出描述 Output Description
这里写图片描述
blob.png
样例输入 Sample Input
这里写图片描述
样例输出 Sample Output
这里写图片描述
这里写图片描述
数据范围及提示 Data Size & Hint

这里写图片描述

此题目有坑!不用在意说什么(u,v)是最短距离,直接从第一个点dfs,每隔一层递加一遍并取max,同时要注意及时取模以免炸int。。(反正我是int存的)。记忆化什么的就不用说了。。这题太水直接贴代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

long long n,p,k,w[200010];
bool vis[200010];
vector <int> edge[200010];

void dfs(int x,int last1,int last2)
{
    vis[x]=1;
    long long t=0,t2=0,t3=0,t4=0;
    for (int i=0;i<edge[x].size();i++)
    {
        int y=edge[x][i];
        if (!vis[y])
        {
            vis[y]=1;
            if (last1!=0)
            {
                k=(k+w[y]*w[last1])%10007;
                p=max(p,w[y]*w[last1]);
            }
            t2+=t*w[y]; t+=w[y];
            if (w[y]>=t3)
            {
                t4=t3; t3=w[y];
            }
            if (w[y]<t3) t4=max(t4,w[y]);
            dfs(y,x,last1);
        }
    }
    p=max(t3*t4,p); k=(k+t2)%10007;
}

int main()
{
    cin>>n;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i=1;i<=n;i++) cin>>w[i];
    dfs(1,0,0);
    cout<<p<<' '<<k*2%10007<<endl;
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49180533

上一篇: P1134阶乘问题
下一篇: 靶形数独
机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
最小生成树问题(Minimum Spanning Trees, MST)

版权声明:本文为博主原创文章,欢迎转载,但请注明出处,谢谢愿意分享知识的你~~ https://blog.csdn.net/qq_32690999/article/details/83988557 最小生成树问题(Minimum Spanning Trees, M...

蓝色枫魂
2018/11/12
0
0
管理日志-原创理论工具--技能方格图

假如我们用椭圆表示只是点,以及扩展开来的领域 来表示相关知识 图A 图B 图B比图A多了一个知识点D,并且与B有重合。 如果这个表示两个人的知识阅历的话,第二个人很明显比第一个人阅历丰富。...

yjplxq
2012/07/16
0
0
传统机器学习回忆笔记

子曰温故而知新; pLSA和LDA 先提几个问题: 1:LDA里面如何算topics之间的距离,进一步,如何根据topics之间的距离确定最优的topics的数量? 2:为什么EM算法可以用来估计pLSA的参数,但是一...

斐斐晏
2017/08/09
0
0
Deep Learning(深度学习)学习笔记整理系列之(六)

目录: 一、概述 二、背景 三、人脑视觉机理 四、关于特征 4.1、特征表示的粒度 4.2、初级(浅层)特征表示 4.3、结构性特征表示 4.4、需要有多少个特征? 五、Deep Learning的基本思想 六、...

云栖希望。
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring mvc主流程源码阅读(剖析)

第一步,通过web.xml的配置可以知道,用户访问url第一次先走到DispatchServlet,(默认你学过基本的java的Servlet开发) <servlet><servlet-name>springServlet</servlet-name><serv......

小海bug
2分钟前
0
0
vmstat命令详解

https://www.cnblogs.com/ggjucheng/archive/2012/01/05/2312625.html

流光韶逝
37分钟前
1
0
如何理解算法时间复杂度的表示

先从O(1) 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键 字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执...

yky20190625
53分钟前
5
0
分布式架构 实现分布式锁的常见方式

一、我们为什么需要分布式锁? 在单机时代,虽然不需要分布式锁,但也面临过类似的问题,只不过在单机的情况下,如果有多个线程要同时访问某个共享资源的时候,我们可以采用线程间加锁的机制...

太猪-YJ
今天
8
0
GitLab Docker 安装记录

安装环境 环境Centos7.4 64 1.拉取镜像文件 docker pull gitlab/gitlab-ce:latest 2.docker 安装 git.zddts.com 为访问域名或换成可以访问的IP docker run -d --hostname git.***.com -p ......

侠者圣
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部