P1099 [NOIP2007 提高组] 树网的核 - 树的直径
2021/7/7 23:09:18
本文主要是介绍P1099 [NOIP2007 提高组] 树网的核 - 树的直径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题解
首先可以发现,如果原树有多条直径,那么在任意一条直径上求得的答案都是一样的。
于是任选一条直径 \(s\leftrightarrow t\),令原树以 \(s\) 为根,在这条直径上枚举答案。
这时候实际上可以用 dfs 序+线段树做到 \(O(n \log n)\),但不够优。
我们知道,树的直径有这样一个性质:任选在直径上的一个点 \(u\),那么满足 \(\operatorname{LCA}(u,v)\in s\leftrightarrow \operatorname{fa}(u)\) 的所有点 \(v\),\(\operatorname{dist}(u,v)\) 一定小于等于 \(\operatorname{dist}(u,s)\)。
对所有在直径上的 \(u\),预处理 \(d_u\) 表示从 \(u\) 开始,不经过直径上的其他点,得到的最长路径。于是,当枚举的路径是 \(u\leftrightarrow v\) 时,答案就是 \(\max\{\max\limits_{x\in u\leftrightarrow v} \{d_x\} ,\operatorname{dist}(s,u),\operatorname{dist}(v,t)\}\),可以用单调队列维护。
但,根据直径的性质,\(\max\limits_{x\in u\leftrightarrow v} \{d_x\}=\max\limits_{x\in s\leftrightarrow t}\{d_x\}\),可以预先算出来。
这样就可以做到 \(O(n)\) 了。
代码
#include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> using namespace std; #define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti) #define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti) template<typename T> void Read(T &x){ x=0;int _f=1; char ch=getchar(); while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar(); while(isdigit(ch)) x=x*10+(ch^48),ch=getchar(); x=x*_f; } template<typename T,typename... Args> void Read(T &x,Args& ...others){ Read(x);Read(others...); } typedef long long ll; const int N=5e5+5; int n,s;vector<pair<int,ll>> G[N]; ll dep[N]; int Diameter(int u,int fa){ int res=u; for(auto i:G[u]){ int v=i.first,x; if(v==fa) continue; dep[v]=dep[u]+i.second; if(dep[x=Diameter(v,u)]>dep[res]) res=x; } return res; } int fa[N]; void Dfs(int u){ for(auto i:G[u]){ if(i.first==fa[u]) continue; fa[i.first]=u,dep[i.first]=dep[u]+i.second; Dfs(i.first); } } int vis[N]; vector<int> pth;ll mxdep[N]; void Dfs1(int u,ll d){ mxdep[u]=d; for(auto i:G[u]){ int v=i.first; if(v==fa[u]||vis[v]) continue; Dfs1(v,d+i.second);mxdep[u]=max(mxdep[u],mxdep[v]); } } int main(){ Read(n,s); For(i,1,n-1){ int u,v,w;Read(u,v,w); G[u].push_back({v,w}),G[v].push_back({u,w}); } int st=Diameter(1,0),ed=Diameter(st,0); // printf("%d %d\n",st,ed); dep[st]=0;Dfs(st); // For(i,1,n) printf("%lld ",dep[i]);puts(""); for(int u=ed;u!=st;u=fa[u]){ pth.push_back(u),vis[u]=1; } pth.push_back(st),vis[st]=1; reverse(pth.begin(),pth.end()); for(int u:pth) Dfs1(u,0); // For(i,1,n) printf("%lld ",mxdep[i]);puts(""); ll mx=0; for(int u:pth) mx=max(mx,mxdep[u]); ll ans=0x3f3f3f3f3f3f3f3fLL,d1=0,d2=dep[ed]; for(int i=0,j=0;i<pth.size()&&j<pth.size();++i){ d1=dep[pth[i]]; while(j<pth.size()&&dep[pth[j]]-dep[pth[i]]<=s) d2=dep[ed]-dep[pth[j++]]; --j; // printf("%d %d %lld %lld\n",i,j,d1,d2); ans=min(ans,max({mx,d1,d2})); } printf("%lld\n",ans); return 0; }
这篇关于P1099 [NOIP2007 提高组] 树网的核 - 树的直径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)