题解

二分时间

然后一个显然的事是一个军队向上爬的越高它控制的点越多

所以首先军队尽量往上爬。

当一个军队可以爬到根节点我们记录下它的剩余时间T和它到达根结点时经过的根节点的子节点son。

当一个军队爬不到根节点时我们就让它控制它可以爬到的最高点。

然后我们把爬到根节点的军队按T从小到大排序。

然后按顺序处理

然后假如一个军队没有时间回到它的son,且son还没有控制。就让它控制son。

因为让别的军队去控制它显然更浪费时间。

否则贪心地匹配就好了(尽量小的和小的和匹配)

然后向上爬用倍增来优化。

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> > q1,q2;
const int N=;
int cnt,head[N],fa[N][],s[N][],top[N],book[N],xb[N],ww[N],www[N],n,m;
long long rest[N];
struct edge{
int nxt,to,w;
}e[];
struct node{
int id,xb;
long long rest;
}k[N];
bool cmp(node a,node b){
return a.rest<b.rest;
}
void add(int u,int v,int w){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
void dfs(int u,int f,int fl){
fa[u][]=f;
s[u][]=fl;
for(int i=;i<=;i++){
fa[u][i]=fa[fa[u][i-]][i-];
s[u][i]=s[fa[u][i-]][i-]+s[u][i-];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
dfs(v,u,e[i].w);
}
}
void dfs1(int u,int f,int tp){
top[u]=tp;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
dfs1(v,u,tp);
}
}
void dfs2(int u,int f){
if(book[u]==)return;
book[u]=;
bool flag=false;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
dfs2(v,u);
if(book[v]==)book[u]=;
flag=true;
}
if(!flag)book[u]=;
}
bool pd(long long maxx){
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
for(int i=;i<=n;i++)book[i]=;
for(int i=;i<=m;i++){
k[i].xb=ww[i];
k[i].rest=maxx;
k[i].id=i;
for(int j=;j>=;j--){
if(fa[k[i].xb][j]&&k[i].rest>=s[k[i].xb][j]){
k[i].rest-=s[k[i].xb][j];
k[i].xb=fa[k[i].xb][j];
}
}
}
sort(k+,k++m,cmp);
for(int i=;i<=m;i++){
if(k[i].xb!=)book[k[i].xb]=;
}
dfs2(,);
for(int i=;i<=m;i++){
if(k[i].xb==&&k[i].rest<www[top[ww[k[i].id]]]&&book[top[ww[k[i].id]]]==)book[top[ww[k[i].id]]]=;
else if(k[i].xb==&&(k[i].rest>=www[top[ww[k[i].id]]]||(k[i].rest<www[top[ww[k[i].id]]]&&book[top[ww[k[i].id]]])))q1.push(k[i].rest);
}
if(book[])return true;
for(int i=head[];i;i=e[i].nxt){
if(book[e[i].to]==)q2.push(e[i].w);
}
while(!q2.empty()){
int a=q2.top();
q2.pop();
while(!q1.empty()&&q1.top()<a)q1.pop();
if(q1.empty())return false;
q1.pop();
}
return true;
}
int main(){
scanf("%d",&n);
for(int i=,u,v,w;i<=n-;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=head[];i;i=e[i].nxt){
www[e[i].to]=e[i].w;
dfs1(e[i].to,,e[i].to);
}
dfs(,,);
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d",&ww[i]);
}
long long l=,r=,ans;
while(l<=r){
long long mid=(l+r)>>;
if(pd(mid)){
r=mid-;
ans=mid;
}
else l=mid+;
}
if(r==)printf("-1");
else printf("%lld",ans);
return ;
}

最新文章

  1. jquery选项卡
  2. MathType 6.9 介绍安装
  3. AC日记——字符串位移包含问题 1.7 19
  4. 结合C++和GDAL实现shapefile(shp)文件的创建和写入
  5. [LeetCode]题解(python):078 Subsets
  6. POJ 3074 Sudoku (Dancing Links)
  7. AIR 程序开发系列 之五 保存数据的几种方式
  8. iOS 开发中的争议(二)
  9. Highcharts下载与使用_数据报表图2
  10. ZOJ1372 POJ 1287 Networking 网络设计 Kruskal算法
  11. SQL server 和Oracle 序列
  12. Swift - 类型判断is 与 类型转换as
  13. 纯注解快速使用spring IOC容器
  14. Hadoop2.7.5+Hbase1.4.0完全分布式
  15. Map的四种遍历
  16. java知识随笔
  17. 笔记《JavaScript 权威指南》(第6版) 分条知识点概要3—表达式和运算符
  18. get() got an unexpected keyword argument
  19. Qt 设置窗口居中显示和窗体大小
  20. ios表单上传图片或文件

热门文章

  1. 相辅相成的求最单源短路径算法:(SPFA&amp; dijkstra)
  2. autocomplete=&quot;off&quot; 不起作用解决方案
  3. Nashorn——在JDK 8中融合Java与JavaScript之力--转
  4. 解决Mysql报错:PHP Warning: mysql_connect(): mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication.
  5. Oracle查询当前用户下的所有表及sqlplus 设置 列宽
  6. 启动tomcat运行maven工程报错:Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:2.3.2:
  7. 爬虫来啦!Day91
  8. docker-ce-17.03.2 离线安装RPM包
  9. python基础8(装饰器)
  10. 嵌入式(C)笔试题