HHHOJ #246 卡车 题解--zhengjun
2022/6/11 23:50:53
本文主要是介绍HHHOJ #246 卡车 题解--zhengjun,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目传送门
题目大意
给定一个 \(n\) 个点的树,每个点有权值 \(v_i\),每条边也有权值 \(w_j\),对于树上一条简单路径,它的权值就是路径上(包括两端点)\(\min{\{v_i\}}\times\sum w_j\),求最大的路径权值。
思路
显然可以发现可以将每个点按照 \(a_i\) 从大到小排序,枚举当前的 \(\min\{v_i\}\),然后发现原来的树会分成若干个连通块,只需要维护出每个连通块的直径即可。
合并连通块的时候,用左边直径的两个端点,和右边直径的两个端点,一共四个点,那么合并完的直径端点必然在这些点当中,所以枚举 \(6\) 种情况即可。
代码
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int N=2e5+10,K=log2(N)+2;vector<pair<int,int> >e[N]; int n,k,a[N],head[N],kk,f[K][N],dep[N],p[N][2],t[4],fa[N],cur[N];ll d[N],mx,ans; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void dfs(int u){for(auto [v,w]:e[u])if(v^f[0][u])f[0][v]=u,dep[v]=dep[u]+1,d[v]=d[u]+w,dfs(v);} void init(){for(int i=1;(1<<i)<=n;i++)for(int j=1;j<=n;j++)f[i][j]=f[i-1][f[i-1][j]];} int LCA(int u,int v){ if(dep[u]<dep[v])swap(u,v);for(int i=k;i>=0;i--)if(dep[f[i][u]]>=dep[v])u=f[i][u]; if(u==v)return u;for(int i=k;i>=0;i--)if(f[i][u]!=f[i][v])u=f[i][u],v=f[i][v];return f[0][u]; } ll dis(int u,int v){int fa=LCA(u,v);return d[u]+d[v]-(d[fa]<<1);} void merge(int u,int v){ u=find(u);v=find(v);tuple<ll,int,int>h[6];t[0]=p[u][0];t[1]=p[u][1];t[2]=p[v][0];t[3]=p[v][1]; int now=0;for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)h[++now]={dis(t[i],t[j]),t[i],t[j]}; h[0]=max(h[0],max(h[1],max(h[2],max(h[3],max(h[4],h[5]))))); mx=max(mx,get<0>(h[0]));p[u][0]=get<1>(h[0]);p[u][1]=get<2>(h[0]);fa[v]=u; } int main(){ scanf("%d",&n);k=log2(n);for(int i=1;i<=n;i++)scanf("%d",&a[fa[i]=cur[i]=p[i][0]=p[i][1]=i]); for(int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),e[u].push_back({v,w}),e[v].push_back({u,w}); dfs(1);init();sort(cur+1,cur+1+n,[](int x,int y){return a[x]>a[y];});for(int i=1,u;u=cur[i],i<=n;i++){ for(auto [v,w]:e[u])if(a[v]>=a[u]&&find(u)^find(v))merge(u,v);ans=max(ans,a[u]*mx);}cout<<ans;return 0; }
如有问题请指出,谢谢--zhengjun
这篇关于HHHOJ #246 卡车 题解--zhengjun的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)