題目鏈接

\(Description\)

給定一棵樹。每次詢問給定\(a\sim b,c\sim d\)兩個下標區間，從這兩個區間中各取一個點，使得這兩個點距離最遠。輸出最遠距離。
\(n,q\leq10^5\)。

\(Solution\)

一個集合直徑的兩端點，在被劃分為兩個集合后一定是兩個集合直徑的四個端點中的兩個。
即假設將\(S\)分為兩個集合后，另外兩個集合的直徑的兩端點分別為a,b和c,d，那么\(S\)集合的直徑的兩端點一定是a,b,c,d中的兩個。（前提是邊權非負）
證明類似樹的直徑。
所以信息可以合并，所以就可以線段樹啦。而且沒有修改，ST表就夠啦。

原來是兩個區間各選一點。。=-=
寫namespace不想改了...有點丑不要介意。

Update：RMQ和ST表還能優化。

---

ST表：

//500ms 44,948KB #include <cstdio> #include <cctype> #include <algorithm> #define BIT 17//2^{17}=131072 //#define gc() getchar() #define MAXIN 500000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=2e5+5;//2nchar IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } namespace PRE {int Enum,H[N>>1],nxt[N],to[N],len[N],dis[N>>1],pos[N>>1],Log2[N],st[N][BIT+1];inline void AE(int w,int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;}inline int LCA_dis(int l,int r){if(l>r) std::swap(l,r);int k=Log2[r-l+1];return std::min(st[l][k],st[r-(1<<k)+1][k])<<1; // return dis[ref[std::min(st[l][k],st[r-(1<<k)+1][k])]]<<1;}inline int Dis(int x,int y){return dis[x]+dis[y]-LCA_dis(pos[x],pos[y]);}void DFS(int x,int fa){static int tot=0;st[pos[x]=++tot][0]=dis[x];//邊權為正的話可以直接用dis[x]for(int i=H[x],v; i; i=nxt[i])if((v=to[i])!=fa) dis[v]=dis[x]+len[i], DFS(v,x), st[++tot][0]=dis[x];}void Init_RMQ(const int n){for(int i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1;for(int j=1; j<=Log2[n]; ++j)for(int t=1<<j-1,i=n-t; i; --i)st[i][j]=std::min(st[i][j-1],st[i+t][j-1]);} } namespace SOL {struct Node{int x,y;}A[N>>1][BIT];using PRE::Log2;Node Merge(const Node &a,const Node &b){int x=a.x,y=a.y,X=b.x,Y=b.y,tx=x,ty=y,tmx=PRE::Dis(x,y),tmp;if((tmp=PRE::Dis(X,Y))>tmx) tmx=tmp,tx=X,ty=Y;if((tmp=PRE::Dis(x,X))>tmx) tmx=tmp,tx=x,ty=X;if((tmp=PRE::Dis(x,Y))>tmx) tmx=tmp,tx=x,ty=Y;if((tmp=PRE::Dis(y,X))>tmx) tmx=tmp,tx=y,ty=X;if((tmp=PRE::Dis(y,Y))>tmx) tmx=tmp,tx=y,ty=Y;return (Node){tx,ty};}inline Node Query(int l,int r){int k=Log2[r-l+1];return Merge(A[l][k],A[r-(1<<k)+1][k]);}void Init_ST(const int n){for(int i=1; i<=n; ++i) A[i][0]=(Node){i,i};for(int j=1; j<=Log2[n]; ++j)for(int t=1<<j-1,i=n-t; i; --i)A[i][j]=Merge(A[i][j-1],A[i+t][j-1]);}void Solve(const int n){Init_ST(n);for(int Q=read(); Q--; ){int a=read(),b=read(),c=read(),d=read();Node X=Query(a,b),Y=Query(c,d);printf("%d\n",std::max(PRE::Dis(X.x,Y.x),std::max(PRE::Dis(X.x,Y.y),std::max(PRE::Dis(X.y,Y.x),PRE::Dis(X.y,Y.y)))));}} }int main() {int n=read();for(int i=1; i<n; ++i) PRE::AE(read(),read(),read());PRE::DFS(1,1), PRE::Init_RMQ(2*n-1), SOL::Solve(n);return 0; }

---

線段樹：

//671ms 45,244KB #include <cstdio> #include <cctype> #include <algorithm> #define BIT 17 #define gc() getchar() #define MAXIN 100000 //#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=2e5+5;//2nchar IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } namespace PRE {int Enum,H[N>>1],nxt[N],to[N],len[N],dis[N>>1],pos[N>>1],Log2[N],st[N][BIT+1];inline void AE(int w,int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;}inline int LCA_dis(int l,int r){if(l>r) std::swap(l,r);int k=Log2[r-l+1];return std::min(st[l][k],st[r-(1<<k)+1][k])<<1; // return dis[ref[std::min(st[l][k],st[r-(1<<k)+1][k])]]<<1;}inline int Dis(int x,int y){return dis[x]+dis[y]-LCA_dis(pos[x],pos[y]);}void DFS(int x,int fa){static int tot=0;st[pos[x]=++tot][0]=dis[x];//邊權為正的話可以直接用dis[x]for(int i=H[x],v; i; i=nxt[i])if((v=to[i])!=fa) dis[v]=dis[x]+len[i], DFS(v,x), st[++tot][0]=dis[x];}void Init_RMQ(const int n){for(int i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1;for(int j=1; j<=Log2[n]; ++j)for(int t=1<<j-1,i=n-t; i; --i)st[i][j]=std::min(st[i][j-1],st[i+t][j-1]);} } struct Segment_Tree {#define ls rt<<1#define rs rt<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define S N<<1//2nint n,ansx,ansy,ansmx,X[S],Y[S],mxds[S];#undef Svoid Merge(int &x,int &y,int &mx,int X,int Y,int Mx){int tmp,tx=x,ty=y,tmx=mx;if(Mx>tmx) tmx=Mx,tx=X,ty=Y;if((tmp=PRE::Dis(x,X))>tmx) tmx=tmp,tx=x,ty=X;if((tmp=PRE::Dis(x,Y))>tmx) tmx=tmp,tx=x,ty=Y;if((tmp=PRE::Dis(y,X))>tmx) tmx=tmp,tx=y,ty=X;if((tmp=PRE::Dis(y,Y))>tmx) tmx=tmp,tx=y,ty=Y;x=tx, y=ty, mx=tmx;}inline void Update(int rt){int l=ls,r=rs;Merge(X[rt]=X[l],Y[rt]=Y[l],mxds[rt]=mxds[l],X[r],Y[r],mxds[r]);}void Build(int l,int r,int rt){if(l==r) {X[rt]=Y[rt]=l; return;}int m=l+r>>1; Build(lson), Build(rson), Update(rt);}void Query(int l,int r,int rt,int L,int R){if(L<=l && r<=R) {Merge(ansx,ansy,ansmx,X[rt],Y[rt],mxds[rt]); return;}int m=l+r>>1;if(L<=m) Query(lson,L,R);if(m<R) Query(rson,L,R);}void Solve(){int a=read(),b=read(),c=read(),d=read();ansx=a, ansy=a, ansmx=0;Query(1,n,1,a,b);int x1=ansx,y1=ansy; ansx=c, ansy=c, ansmx=0;Query(1,n,1,c,d);int x2=ansx,y2=ansy;printf("%d\n",std::max(PRE::Dis(x1,x2),std::max(PRE::Dis(x1,y2),std::max(PRE::Dis(y1,x2),PRE::Dis(y1,y2)))));} }T;int main() {int n=read();for(int i=1; i<n; ++i) PRE::AE(read(),read(),read());PRE::DFS(1,1), PRE::Init_RMQ(2*n-1);T.n=n, T.Build(1,n,1);for(int Q=read(); Q--; T.Solve());return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/10090344.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的51Nod.1766.树上最远点对(树的直径 RMQ 线段树/ST表)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。