首页 > 代码库 > 51Nod 1766 树上的最远点对
51Nod 1766 树上的最远点对
Description
一棵树,询问两个端点编号分别在在 \([a,b]\) 和 \([c,d]\) 两个区间中的最长链.
Sol
线段树+ST表.
树上最长链可以合并,只需要合并两个区间最长链的两个端点即可.
ST表要预处理好 \(log\) ,用了cmath 的 log2() ,T的飞起.
Code
#include<cstdio>#include<cmath>#include<cstring>#include<utility>#include<vector>#include<iostream>using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "#define mpr make_pairtypedef pair< int,int > pr;typedef long long LL;const int N = 100050;const int M = 25;int n,m,cnt;vector< pr > g[N];int pow2[M],lg2[N<<1],dfs[N<<1],d[N],val[N],pos[N];int f[N<<1][M];inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }void DFS(int u,int fa,int dep,int value){ dfs[++m]=u,d[u]=dep,val[u]=value,pos[u]=m,f[m][0]=u; for(int i=0,v,lim=g[u].size();i<lim;i++) if((v=g[u][i].first)!=fa) DFS(v,u,dep+1,value+g[u][i].second),dfs[++m]=u,f[m][0]=u;}void init(){ pow2[0]=1;for(int i=1;i<M;i++) pow2[i]=pow2[i-1]<<1; lg2[0]=-1;for(int i=1;i<=m;i++) lg2[i]=lg2[i>>1]+1; for(int j=1;j<M;j++) for(int i=1;i<=m;i++) if(i+pow2[j]-1<=m){ int u=f[i][j-1],v=f[i+pow2[j-1]][j-1]; if(d[u]<d[v]) f[i][j]=u;else f[i][j]=v; }}int Dis(int u,int v,int lca=0){ if(pos[u]<pos[v]) swap(u,v);int lg=lg2[pos[u]-pos[v]+1]; if(d[f[pos[v]][lg]]<d[f[pos[u]-pow2[lg]+1][lg]]) lca=f[pos[v]][lg];else lca=f[pos[u]-pow2[lg]+1][lg]; return (LL)val[u]+val[v]-2*val[lca];}struct SegmentTree{ #define lc (o<<1) #define rc (o<<1|1) #define mid ((l+r)>>1) #define Gd(u) Dis(u.first,u.second) pr g[N<<2];int d[N<<2]; pr PushUp(pr u,pr v,int d1=0,int d2=0,int o=0){ if(!d1 && !d2) d1=Gd(u),d2=Gd(v); pr res=d1>d2?u:v;int dd=max(d1,d2); if(Dis(u.first,v.first)>dd) res=mpr(u.first,v.first),dd=Gd(res); if(Dis(u.first,v.second)>dd) res=mpr(u.first,v.second),dd=Gd(res); if(Dis(u.second,v.first)>dd) res=mpr(u.second,v.first),dd=Gd(res); if(Dis(u.second,v.second)>dd) res=mpr(u.second,v.second),dd=Gd(res); if(o) d[o]=dd;return res; } void Build(int o,int l,int r){ if(l==r){ g[o]=mpr(l,l),d[o]=0;return; } Build(lc,l,mid);Build(rc,mid+1,r); g[o]=PushUp(g[lc],g[rc],d[lc],d[rc],o); } pr Query(int o,int l,int r,int L,int R){ if(L<=l && r<=R) return g[o]; pr res=mpr(L,L); if(L<=mid) res=Query(lc,l,mid,L,R); if(R>mid) res=PushUp(res,Query(rc,mid+1,r,L,R)); return res; } pr Merge(pr u,pr v){ pr res=mpr(u.first,v.first);int d=Gd(res); if(Dis(u.first,v.second)>d) res=mpr(u.first,v.second),d=Gd(res); if(Dis(u.second,v.first)>d) res=mpr(u.second,v.first),d=Gd(res); if(Dis(u.second,v.second)>d) res=mpr(u.second,v.second),d=Gd(res); return res; } int Query(int a,int b,int c,int d){ pr r1=Query(1,1,n,a,b),r2=Query(1,1,n,c,d),r3=Merge(r1,r2); return Gd(r3); } #undef lc #undef rc #undef mid #undef Gd}seg;int main(){ n=in();memset(d,0x3f,sizeof(d)); for(int i=1,u,v,w;i<n;i++) u=in(),v=in(),w=in(),g[u].push_back(mpr(v,w)),g[v].push_back(mpr(u,w)); DFS(1,1,1,0),init(),seg.Build(1,1,n); for(int k=in(),a,b,c,d;k--;){ a=in(),b=in(),c=in(),d=in(); printf("%d\n",seg.Query(a,b,c,d)); }return 0;}
51Nod 1766 树上的最远点对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。