題意：給定一個樹（10^5），m個詢問（10^5），每次給定a，b，c，d，在區間[a，b]中選一個點，[c，d]選一個點，使得這兩個點距離最大，輸出最大距離。

題解：首先，我們有一個結論：對于一個集合的直徑，如果我們將這個集合分解成兩個非空集合，它的端點一定在兩個非空集合的兩個端這4個端點中。這非常的顯然。。。

那么我們就可以做到合并兩個集合，我們就可以用線段樹維護每個區間的直徑，就好啦，完全不用復雜的數據結構。

這道題卡時間，所以LCA要用歐拉序RMQ做。

復雜度O（nlogn）

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 inline int read(){ 5 int x=0,f=1; char a=getchar(); 6 while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();} 7 while(a>='0' && a<='9') x=x*10+a-'0',a=getchar(); 8 return x*f; 9 } 10 int n,m,cnt=1,euler[2*N],dep[N],head[N],fi[N],dis[N],st[N][20],mn[N][20],Log[2*N]; 11 struct edges{ 12 int to,c,next; 13 }e[N]; 14 struct node{ 15 int x1,x2,l,r; 16 }seg[4*N]; 17 struct data{ 18 int x1,x2; 19 }; 20 inline int getdis(int u,int v){ 21 if(!u || !v) return 0; 22 u=fi[u]; v=fi[v]; 23 if(u>v) swap(u,v); 24 int p,len=Log[v-u+1]; 25 p=mn[u][len]<mn[v-(1<<len)+1][len]?st[u][len]:st[v-(1<<len)+1][len]; 26 return dis[euler[u]]+dis[euler[v]]-2*dis[p]; 27 } 28 inline void update(int x){ 29 int mx=0,x1=seg[x<<1].x1,x2=seg[x<<1].x2,x3=seg[x<<1|1].x1,x4=seg[x<<1|1].x2,f; 30 if((f=getdis(x1,x2))>mx) seg[x].x1=x1,seg[x].x2=x2,mx=f; if((f=getdis(x1,x3))>mx) seg[x].x1=x1,seg[x].x2=x3,mx=f; 31 if((f=getdis(x1,x4))>mx) seg[x].x1=x1,seg[x].x2=x4,mx=f; if((f=getdis(x2,x3))>mx) seg[x].x1=x2,seg[x].x2=x3,mx=f; 32 if((f=getdis(x2,x4))>mx) seg[x].x1=x2,seg[x].x2=x4,mx=f; if((f=getdis(x3,x4))>mx) seg[x].x1=x3,seg[x].x2=x4,mx=f; 33 } 34 inline void insert(){ 35 int u=read(),v=read(),c=read(); 36 e[++cnt]=(edges){v,c,head[u]};head[u]=cnt; 37 } 38 void dfs(int x,int fa){ 39 dep[x]=dep[fa]+1; fi[x]=euler[0]+1; 40 for(int i=head[x];i;i=e[i].next){ 41 if(fa==e[i].to) continue; 42 euler[++euler[0]]=x; 43 dis[e[i].to]=dis[x]+e[i].c; dfs(e[i].to,x); 44 } 45 euler[++euler[0]]=x; 46 } 47 inline void rmq_pre(){ 48 for(int i=1;i<=euler[0];i++) st[i][0]=euler[i],mn[i][0]=dep[euler[i]]; 49 for(int i=1;i<=18;i++) 50 for(int j=1;j<=euler[0];j++){ 51 if(j+(1<<i)-1>euler[0]) break; 52 if(mn[j][i-1]<mn[j+(1<<(i-1))][i-1]) st[j][i]=st[j][i-1],mn[j][i]=mn[j][i-1]; 53 else st[j][i]=st[j+(1<<(i-1))][i-1],mn[j][i]=mn[j+(1<<(i-1))][i-1]; 54 } 55 Log[0]=-1; for(int i=1;i<=euler[0];i++) Log[i]=Log[i>>1]+1; 56 } 57 void build(int l,int r,int x){ 58 seg[x].l=l; seg[x].r=r; 59 if(l==r) {seg[x].x1=l; seg[x].x2=0; return;} 60 int mid=(l+r)>>1; 61 build(l,mid,x<<1); 62 build(mid+1,r,x<<1|1); 63 update(x); 64 } 65 data merge(data tmp1,data tmp2){ 66 int f,mx=0,x1=tmp1.x1,x2=tmp1.x2,x3=tmp2.x1,x4=tmp2.x2; 67 data ret; 68 if((f=getdis(x1,x2))>mx) ret.x1=x1,ret.x2=x2,mx=f; if((f=getdis(x1,x3))>mx) ret.x1=x1,ret.x2=x3,mx=f; 69 if((f=getdis(x1,x4))>mx) ret.x1=x1,ret.x2=x4,mx=f; if((f=getdis(x2,x3))>mx) ret.x1=x2,ret.x2=x3,mx=f; 70 if((f=getdis(x2,x4))>mx) ret.x1=x2,ret.x2=x4,mx=f; if((f=getdis(x3,x4))>mx) ret.x1=x3,ret.x2=x4,mx=f; 71 return ret; 72 } 73 data query(int L,int R,int x){ 74 int l=seg[x].l,r=seg[x].r; 75 if(l==L && r==R) {return (data){seg[x].x1,seg[x].x2};} 76 int mid=(l+r)>>1; 77 if(R<=mid) return query(L,R,x<<1); 78 else if(mid<L) return query(L,R,x<<1|1); 79 else return merge(query(L,mid,x<<1),query(mid+1,R,x<<1|1)); 80 } 81 int main(){ 82 n=read(); 83 for(int i=1;i<n;i++) insert(); 84 dfs(1,0); rmq_pre(); build(1,n,1); 85 m=read(); 86 while(m--){ 87 int t1,t2,a=read(),b=read(),c=read(),d=read(); 88 data tmp1=query(a,b,1),tmp2=query(c,d,1); 89 t1=max(getdis(tmp1.x1,tmp2.x1),getdis(tmp1.x1,tmp2.x2)); 90 t2=max(getdis(tmp1.x2,tmp2.x1),getdis(tmp1.x2,tmp2.x2)); 91 printf("%d\n",max(t1,t2)); 92 } 93 return 0; 94 }

?

轉載于:https://www.cnblogs.com/enigma-aw/p/6344784.html

總結

以上是生活随笔為你收集整理的51nod 1766的全部內容，希望文章能夠幫你解決所遇到的問題。

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