鹰潭市建设局网站,澄海区建设局网站,短视频运营招聘,内容营销概念题目链接 \(Description\) 给定一棵树。每次询问给定\(a\sim b,c\sim d\)两个下标区间#xff0c;从这两个区间中各取一个点#xff0c;使得这两个点距离最远。输出最远距离。\(n,q\leq10^5\)。 \(Solution\) 一个集合直径的两端点#xff0c;在被划分为两个集合后一定是两个…题目链接 \(Description\) 给定一棵树。每次询问给定\(a\sim b,c\sim d\)两个下标区间从这两个区间中各取一个点使得这两个点距离最远。输出最远距离。\(n,q\leq10^5\)。 \(Solution\) 一个集合直径的两端点在被划分为两个集合后一定是两个集合直径的四个端点中的两个。 即假设将\(S\)分为两个集合后另外两个集合的直径的两端点分别为a,b和c,d那么\(S\)集合的直径的两端点一定是a,b,c,d中的两个。前提是边权非负 证明类似树的直径。 所以信息可以合并所以就可以线段树啦。而且没有修改ST表就够啦。 原来是两个区间各选一点。。- 写namespace不想改了...有点丑不要介意。 UpdateRMQ和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() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N2e55;//2nchar IN[MAXIN],*SSIN,*TTIN;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
namespace PRE
{int Enum,H[N1],nxt[N],to[N],len[N],dis[N1],pos[N1],Log2[N],st[N][BIT1];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(lr) std::swap(l,r);int kLog2[r-l1];return std::min(st[l][k],st[r-(1k)1][k])1;
// return dis[ref[std::min(st[l][k],st[r-(1k)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 tot0;st[pos[x]tot][0]dis[x];//边权为正的话可以直接用dis[x]for(int iH[x],v; i; inxt[i])if((vto[i])!fa) dis[v]dis[x]len[i], DFS(v,x), st[tot][0]dis[x];}void Init_RMQ(const int n){for(int i2; in; i) Log2[i]Log2[i1]1;for(int j1; jLog2[n]; j)for(int t1j-1,in-t; i; --i)st[i][j]std::min(st[i][j-1],st[it][j-1]);}
}
namespace SOL
{struct Node{int x,y;}A[N1][BIT];using PRE::Log2;Node Merge(const Node a,const Node b){int xa.x,ya.y,Xb.x,Yb.y,txx,tyy,tmxPRE::Dis(x,y),tmp;if((tmpPRE::Dis(X,Y))tmx) tmxtmp,txX,tyY;if((tmpPRE::Dis(x,X))tmx) tmxtmp,txx,tyX;if((tmpPRE::Dis(x,Y))tmx) tmxtmp,txx,tyY;if((tmpPRE::Dis(y,X))tmx) tmxtmp,txy,tyX;if((tmpPRE::Dis(y,Y))tmx) tmxtmp,txy,tyY;return (Node){tx,ty};}inline Node Query(int l,int r){int kLog2[r-l1];return Merge(A[l][k],A[r-(1k)1][k]);}void Init_ST(const int n){for(int i1; in; i) A[i][0](Node){i,i};for(int j1; jLog2[n]; j)for(int t1j-1,in-t; i; --i)A[i][j]Merge(A[i][j-1],A[it][j-1]);}void Solve(const int n){Init_ST(n);for(int Qread(); Q--; ){int aread(),bread(),cread(),dread();Node XQuery(a,b),YQuery(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 nread();for(int i1; in; 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() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N2e55;//2nchar IN[MAXIN],*SSIN,*TTIN;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
namespace PRE
{int Enum,H[N1],nxt[N],to[N],len[N],dis[N1],pos[N1],Log2[N],st[N][BIT1];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(lr) std::swap(l,r);int kLog2[r-l1];return std::min(st[l][k],st[r-(1k)1][k])1;
// return dis[ref[std::min(st[l][k],st[r-(1k)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 tot0;st[pos[x]tot][0]dis[x];//边权为正的话可以直接用dis[x]for(int iH[x],v; i; inxt[i])if((vto[i])!fa) dis[v]dis[x]len[i], DFS(v,x), st[tot][0]dis[x];}void Init_RMQ(const int n){for(int i2; in; i) Log2[i]Log2[i1]1;for(int j1; jLog2[n]; j)for(int t1j-1,in-t; i; --i)st[i][j]std::min(st[i][j-1],st[it][j-1]);}
}
struct Segment_Tree
{#define ls rt1#define rs rt1|1#define lson l,m,rt1#define rson m1,r,rt1|1#define S N1//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,txx,tyy,tmxmx;if(Mxtmx) tmxMx,txX,tyY;if((tmpPRE::Dis(x,X))tmx) tmxtmp,txx,tyX;if((tmpPRE::Dis(x,Y))tmx) tmxtmp,txx,tyY;if((tmpPRE::Dis(y,X))tmx) tmxtmp,txy,tyX;if((tmpPRE::Dis(y,Y))tmx) tmxtmp,txy,tyY;xtx, yty, mxtmx;}inline void Update(int rt){int lls,rrs;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(lr) {X[rt]Y[rt]l; return;}int mlr1; Build(lson), Build(rson), Update(rt);}void Query(int l,int r,int rt,int L,int R){if(Ll rR) {Merge(ansx,ansy,ansmx,X[rt],Y[rt],mxds[rt]); return;}int mlr1;if(Lm) Query(lson,L,R);if(mR) Query(rson,L,R);}void Solve(){int aread(),bread(),cread(),dread();ansxa, ansya, ansmx0;Query(1,n,1,a,b);int x1ansx,y1ansy; ansxc, ansyc, ansmx0;Query(1,n,1,c,d);int x2ansx,y2ansy;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 nread();for(int i1; in; i) PRE::AE(read(),read(),read());PRE::DFS(1,1), PRE::Init_RMQ(2*n-1);T.nn, T.Build(1,n,1);for(int Qread(); Q--; T.Solve());return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/10090344.html
