$bzoj3872\ [Poi2014]\ Ant\ colony$ 二分+$dp$

时间：2023-03-09 01:45:17
$bzoj3872\ [Poi2014]\ Ant\ colony$ 二分+$dp$

正解:二分+$dp$

解题报告:

传送门$QwQ$

一年过去了依然没有头绪,,,$gql$的$NOIp$必将惨败了$kk$.

考虑倒推,因为知道知道除数和答案,所以可以推出被除数的范围,然后一路推到叶子节点就成$QwQ$

$over$

嗷注意一个细节是有可能乘爆,所以每次和$m_max$取个$min$就成$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define int long long

#define t(i) edge[i].to

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+;

int n,head[N],ed_cnt,g,K,m[N],frx,fry,in[N],l[N],r[N],inf,as;

struct ed{int to,nxt;}edge[N<<];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri y){edge[++ed_cnt]=(ed){x,head[y]};head[y]=ed_cnt;++in[x];}

void dfs(ri nw,ri fa)

{

    e(i,nw)

        if(t(i)^fa)

            l[t(i)]=min(1ll*l[nw]*(in[nw]-),inf+),r[t(i)]=min(1ll*(r[nw]+)*(in[nw]-)-,inf),dfs(t(i),nw);

}

il int fd1(ri x){return lower_bound(m+,m++g,x)-m-;}

il int fd2(ri x){ri tmp=upper_bound(m+,m++g,x)-m;return m[tmp]==x?tmp:tmp-;}

signed main()

{

    freopen("3872.in","r",stdin);freopen("3872.out","w",stdout);

    n=read();g=read();K=read();rp(i,,g)m[i]=read();sort(m+,m++g);inf=m[g];

    rp(i,,n-){ri x=read(),y=read();ad(x,y);ad(y,x);if(i==)frx=x,fry=y;}

    l[frx]=r[frx]=l[fry]=r[fry]=K;dfs(frx,fry);dfs(fry,frx);

    rp(i,,n)if(in[i]==)as+=fd2(r[i])-fd1(l[i]);;printf("%lld\n",1ll*as*K);

    return ;

}

随机推荐

  1. Javascript 严格模式下不允许删除一个不允许删除的属性

    如下代码,在严格模式下,如果删除 Object.prototype 浏览器会报错,目前 IE10 也支持 严格模式. <script> "use strict"; de ...

  2. PHP 7.0新增特性详解

    https://www.cnblogs.com/riverdubu/archive/2017/03/22/6434705.html 开始介绍PHP7.0新特性,具体的可以参照官网的介绍,我来挑一些给大 ...

  3. html实体字符转换成字符串

    function EntityToString(value) { let tag = document.createElement("div"); tag.innerHTML = ...

  4. 写给初学前端工程师的一封信 - 转载 至https://www.w3ctech.com/topic/983

    以下内容是转载https://www.w3ctech.com/topic/983 大家好: 应波波的邀请写一写我对这个话题的想法.从去年开始不少朋友让我帮忙介绍前端工程师,绝大部分忙都没帮上,原因是真 ...

  5. laravel5.6 发送邮件附带邮件时，Unable to open file for reading，报错文件路径问题

    https://*.com/questions/48568739/unable-to-open-file-for-reading-swift-ioexception-in-la ...

  6. sublime 插件安装packagecontrol

    https://packagecontrol.io/installation 第一步: Installation Simple The simplest method of installation ...

  7. display：flex; justify-content:space-between; 最后一行显示内容无法靠左显示

    给父元素添加同每行展示列数一样(展示列表最多的)的子元素. 子元素设置样式: width:同子元素一样的width : height:0;

  8. angularJS $q

    1.$q $q是Angular的一种内置服务,它可以使你异步地执行函数,并且当函数执行完成时它允许你使用函数的返回值(或异常). 2.defer defer的字面意思是延迟, $q.defer()   ...

  9. 推荐几个web前端比较实用的网站

    第一次写博客,说实在的有点紧张和兴奋,哈哈哈哈,本人工作了有两年的时间,平时也有做笔记的习惯,但是都做得乱七八糟的,所以就想通过写博客来记录.好了,废话不多说了,先来几个觉得在工作中使用到的,还不错的 ...

  10. H3C DCC概念

相关文章