luogu 2491 [SDOI2011]消防 / 1099 树网的核 单调队列 + 树上问题
2024-09-05 21:37:09
Code:
#include<bits/stdc++.h>
#define ll long long
#define maxn 300001
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
deque<int>Q;
int n,S,edges,k;
int hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn<<1],dis[maxn],fa[maxn],mark[maxn];
void add(int u,int v,int c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
void dfs(int u,int ff)
{
if(dis[u]>dis[k]) k=u;
fa[u]=ff;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff || mark[v]) continue;
dis[v]=dis[u]+val[i],dfs(v,u);
}
}
int answer[maxn];
map<int,int>pre,back;
int main()
{
int i,j,x,y;
// setIO("input");
scanf("%d%d",&n,&S);
for(i=1;i<n;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c), add(b,a,c);
}
dis[1]=0, dfs(1,0);
x=k, k=0,dis[x]=0,dfs(x,0),y=k;
//y->x
for(int i=y;i;i=fa[i]) mark[i]=1,pre[i]=dis[i], back[i]=dis[y]-dis[i];
int ans=inf,s=y;
for(int i=y;i;i=fa[i])
{
dis[k=0]=0;
dis[i]=0, dfs(i,fa[i]),answer[i]=dis[k];
while(!Q.empty()&&pre[Q.front()]-pre[i]>S) Q.pop_front();
while(!Q.empty()&&answer[i]>=answer[Q.back()]) Q.pop_back();
while(pre[s]-pre[i]>S) s=fa[s];
Q.push_back(i);
int a=answer[Q.front()];
int b=pre[i];
int c=back[s];
ans=min(ans,max(max(a,b),c));
}
printf("%d\n",ans);
return 0;
}
最新文章
- UVA227
- Qcon会议之所见所想
- Effective Java之避免创建不必要的对象
- 简化版可用于多线程的logger
- 解决UITableView中Cell重用机制导致内容出错的方法总结
- 使用Code::Blocks配置Python编译环境
- shell之小括号、中括号、大括号
- VS2013以管理员身份使用
- .net 生成缩略图
- 决策树模型组合之随机森林与GBDT
- 简单的OC程序
- ORACLE 查询某表中的某个字段的类型,是否为空,是否有默认值等
- Educational Codeforces Round 61 (Rated for Div. 2)-C. Painting the Fence 前缀和优化
- Python爬虫之二
- 利用 Eclipse IDE 的强大功能远程调试 Java 应用程序
- LeetCode算法题-Sum of Left Leaves(Java实现)
- babel-cli 的使用
- js数组去除重复数据
- mysql 启动和关闭外键约束
- 51nod1331 狭窄的通道