BZOJ_3872_[Poi2014]Ant colony_dfs
Description
Input
Output
Sample Input
3 4 1 9 11
1 2
1 4
4 3
4 5
4 6
6 7
Sample Output
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
register int x=0;
register char s=nc();
while(s<'0'||s>'9')s=nc();
while(s>='0'&&s<='9')x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 1000050
typedef long long ll;
int head[N],to[N<<1],nxt[N<<1],out[N],cnt;
int m[N],n,g,k,root1,root2;
ll upper[N],lower[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; out[u]++;
}
void dfs(int x,int y) {
int i;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
upper[to[i]]=upper[x]*(out[x]-1)+out[x]-2;
if(upper[to[i]]<0) upper[to[i]]=m[g];
upper[to[i]]=min(upper[to[i]],1ll*m[g]);
lower[to[i]]=lower[x]*(out[x]-1);
if(lower[to[i]]<=m[g]&&lower[to[i]]>=0)
dfs(to[i],x);
}
}
}
int search(ll x) {
int l=1,r=g+1;
while(l<r) {
int mid=(l+r)>>1;
if(m[mid]<=x) l=mid+1;
else r=mid;
}
return l-1;
}
int main() {
n=rd(); g=rd(); k=rd();
int i,x,y;
for(i=1;i<=g;i++) m[i]=rd();
sort(m+1,m+g+1);
root1=rd(); root2=rd();
add(root1,root2); add(root2,root1);
for(i=2;i<n;i++) {
x=rd(); y=rd();
add(x,y); add(y,x);
}
upper[root1]=upper[root2]=lower[root1]=lower[root2]=k;
dfs(root1,root2);
dfs(root2,root1);
ll ans=0;
for(i=1;i<=n;i++) if(out[i]==1) ans+=search(upper[i])-search(lower[i]-1);
printf("%lld\n",ans*k);
}
BZOJ_3872_[Poi2014]Ant colony_dfs的更多相关文章
-
[BZOJ3872][Poi2014]Ant colony
[BZOJ3872][Poi2014]Ant colony 试题描述 There is an entrance to the ant hill in every chamber with only o ...
-
bzoj 3872: [Poi2014]Ant colony -- 树形dp+二分
3872: [Poi2014]Ant colony Time Limit: 30 Sec Memory Limit: 128 MB Description There is an entranc ...
-
【BZOJ3872】[Poi2014]Ant colony 树形DP+二分
[BZOJ3872][Poi2014]Ant colony Description 给定一棵有n个节点的树.在每个叶子节点,有g群蚂蚁要从外面进来,其中第i群有m[i]只蚂蚁.这些蚂蚁会相继进入树中, ...
-
[bzoj3872][Poi2014]Ant colony_树形dp
Ant colony bzoj-3872 Poi-2014 题目大意:说不明白.....题目链接 注释:略. 想法:两个思路都行. 反正我们就是要求出每个叶子节点到根节点的每个路径权值积. 可以将边做 ...
-
[POI2014]Ant colony
题目大意: 给定一棵$n(n\le10^6)$个结点的树.在每个叶子结点,有$g$群蚂蚁要从外面进来,其中第$i$群有$m_i$只蚂蚁.这些蚂蚁依次爬树(一群蚂蚁爬完后才会爬另一群),若当前经过结点度 ...
-
bzoj 3872 [Poi2014]Ant colony——二分答案
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3872 可以倒推出每个叶子节点可以接受的值域.然后每个叶子二分有多少个区间符合即可. 注意一开 ...
-
bzoj 3872: [Poi2014]Ant colony【树形dp+二分】
啊我把分子分母混了WA了好几次-- 就是从食蚁兽在的边段成两棵树,然后dp下去可取的蚂蚁数量区间,也就是每次转移是l[e[i].to]=l[u](d[u]-1),r[e[i].to]=(r[u]+1) ...
-
$bzoj3872\ [Poi2014]\ Ant\ colony$ 二分+$dp$
正解:二分+$dp$ 解题报告: 传送门$QwQ$ 一年过去了依然没有头绪,,,$gql$的$NOIp$必将惨败了$kk$. 考虑倒推,因为知道知道除数和答案,所以可以推出被除数的范围,然后一路推到叶 ...
-
POI2014题解
POI2014题解 [BZOJ3521][Poi2014]Salad Bar 把p当作\(1\),把j当作\(-1\),然后做一遍前缀和. 一个合法区间\([l,r]\)要满足条件就需要满足所有前缀和 ...
随机推荐
-
[原] Cgroup CPU, Blkio 测试
关于Cgroup的简单测试 [toc] 简单介绍Cgroup (如果对cgroup熟悉可以忽略) 一般情况下,cgroup挂载到一个虚拟文件目录,然后可以通过文件系统的API对其操作. ># m ...
-
(原创)android Sqlite多线程访问异常解决方案
在开发Android的程序的时候sqlite数据库是经常用到的:在多线程访问数据库的时候会出现这样的异常:java.lang.IllegalStateException: Cannot perform ...
-
造成win2008 500内部错误不能显示详细错误的原因和解决方法
造成500错误常见原因有:ASP语法出错.ACCESS数据库连接语句出错.文件引用与包含路径出错.使用了服务器不支持的组件如FSO等. 另外,对于win2008的IIS默认不显示详细出错信息的问题以下 ...
-
用手机或外部设备在同一局域网下访问虚拟主机wampsever的方法版本号是2.4.9
1,首先在虚拟服务器电脑上可以打开http://localhost/ 2,在外部设备访问时报错为:You don't have permission to access / in on this se ...
-
<;自动化测试方案_5>;第五章、代码单元自动化测试
第五章.代码单元自动化测试 代码单元测试需要根据编程语言,选择单元测试框架,然后访问类方法,函数.代码单元测试做自动化,相比API.UI自动化做起来更加麻烦,建议放到待API自动化测试.UI自动化测试 ...
-
OGG-01028 Incompatible Record解决办法
How to recover from an OGG-01028 Incompatible Record if the trail is not corrupt (Doc ID 1507462.1) ...
-
Java网络通信方面,BIO、NIO、AIO、Netty
码云项目源码地址:https://gitee.com/ZhangShunHai/echo 教学视频地址:链接: https://pan.baidu.com/s/1knVlW7O8hZc8XgXm1dC ...
-
4. Median of Two Sorted Arrays (二分法;递归的结束条件)
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two ...
-
QQ开发技术资料集锦
1.GG2013:可在广域网部署运行的QQ高仿版 http://www.cnblogs.com/justnow/category/503400.html 2. 苏飞博客: C#仿QQ皮肤-皮肤控件窗体 ...
-
spm教程
1.spm初学者教程:http://www.ernohermans.com/wp-content/uploads/2011/11/spm8_startersguide.pdf 2.spm官方mannu ...