Social Net ZOJ - 3649 題意： 反正原題題意我是看不懂... 參考：http://www.cnblogs.com/names-yc/p/4922867.html 給出一幅圖，求最大生成樹，輸出邊權之和，併在這棵樹上進行查詢操作：給出兩個結點編號x和y，求從x到y的路徑上，由每個結 ...
題意：
反正原題題意我是看不懂...
參考：http://www.cnblogs.com/names-yc/p/4922867.html
給出一幅圖，求最大生成樹，輸出邊權之和，併在這棵樹上進行查詢操作：給出兩個結點編號x和y，求從x到y的路徑上，由每個結點的權值構成的序列中的極差大小——要求，被減數要在減數的後面，即形成序列{a1,a2…aj …ak…an}，求ak-aj (k>=j)的最大值。
做法：
首先kruskal求一下最大生成樹。然後做倍增dp。
p[i]表示i號節點的權值
anc[i][j]表示i號節點的第2^j級祖先
根據倍增的基本思想，有：
maxn[i][j]表示從i號節點出發向上走，共走過2^j個節點（包含i號節點），這些節點中點權的最大值
$maxn[i][0]=p[i]$
$maxn[i][j]=max(maxn[i][j-1],maxn[anc[i][j-1]][j-1])$
minn[i][j]表示從i號節點出發向上走，共走過2^j個節點（包含i號節點），這些節點中點權的最小值
$minn[i][0]=p[i]$
$minn[i][j]=min(minn[i][j-1],minn[anc[i][j-1]][j-1])$
maxans[i][j]表示從i號節點出發向上走，共走過2^j個節點（包含i號節點），這些節點的權值按經過順序構成的序列{a1,a2…aj …ak…an}中，求ak-aj(k>=j)的最大值。
$maxans[i][0]=0$
$maxans[i][j]=max(maxans[i][j-1],maxans[anc[i][j-1]][j-1],maxn[anc[i][j-1]][j-1]-minn[i][j-1])$
其含義為：最大差值要麼是在前一半產生，要麼在後一半產生，要麼就是後一半的最大值減去前一半的最小值。
minans[i][j]表示從i號節點出發向上走，共走過2^j個節點（包含i號節點），這些節點的權值按經過順序的構成的序列{a1,a2…aj …ak…an}中，求ak-aj(k<=j)的最大值。（這個數組的名字其實不太對...不要管它）
$minans[i][0]=0$
$minans[i][j]=max(minans[i][j-1],minans[anc[i][j-1]][j-1],maxn[i][j-1]-minn[anc[i][j-1]][j-1])$
其含義為：最大差值要麼是在前一半產生，要麼在後一半產生，要麼就是前一半的最大值減去後一半的最小值。
以上都可以在dfs過程中完成。
求結果的過程，也可以視為倍增lca，但是在點“上移”的過程中，要求把移過的部分的答案更新到當前答案上。
設lca(x,y)=z。從x到y的路徑，可以視為x到z，z再到y。那麼，答案就是max(x到z路徑中最大答案,z到y路徑中最大答案,z權值-x到z路徑中最小值,z到y路徑中最大值-z權值,z到y路徑中最大答案-x到z路徑中最大答案)。
在x上移時，上移之後的最大答案就是max(x已經過部分產生的最大答案,將要上移部分的最大值-x已經過部分的最小值,將要上移部分的最大答案(在maxans中取))。
在y上移時，上移之後的最大答案就是max(y已經過部分產生的最大答案,y已經過部分的最大值-將要上移部分的最小值,將要上移部分的最大答案(在minans中取))。
錯誤記錄（本地）：
1.由於x和y有順序，不能寫成形如47行
2.缺少63,64行
3.缺少75-78行，由於按這個方法寫，上移過程中，當前點不會被更新進已有答案
http://www.xuebuyuan.com/1162519.html1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 struct E1 7 { 8 int a,b,w; 9 friend bool operator<(const E1& a,const E1& b) 10 { 11 return a.w>b.w; 12 } 13 }e1[50100]; 14 struct Edge 15 { 16 int to,d,nxt; 17 }e[100100]; 18 int fa[50100],p[50100],n,m,ne,f1[50100],log2n,deep[50100],q,ans1; 19 int minn[50100][17],maxn[50100][17],minans[50100][17],maxans[50100][17],anc[50100][17]; 20 int find(int x) 21 { 22 return fa[x]==x?x:fa[x]=find(fa[x]); 23 } 24 void dfs(int x,int fa) 25 { 26 int i,k; 27 minn[x][0]=maxn[x][0]=p[x]; 28 //minans[x][0]=maxans[x][0]=0; 29 for(i=1;i<=log2n;i++) 30 { 31 anc[x][i]=anc[anc[x][i-1]][i-1]; 32 minn[x][i]=min(minn[x][i-1],minn[anc[x][i-1]][i-1]); 33 maxn[x][i]=max(maxn[x][i-1],maxn[anc[x][i-1]][i-1]); 34 minans[x][i]=max(max(minans[anc[x][i-1]][i-1],minans[x][i-1]),maxn[x][i-1]-minn[anc[x][i-1]][i-1]); 35 maxans[x][i]=max(max(maxans[anc[x][i-1]][i-1],maxans[x][i-1]),maxn[anc[x][i-1]][i-1]-minn[x][i-1]); 36 } 37 for(k=f1[x];k!=0;k=e[k].nxt) 38 if(e[k].to!=fa) 39 { 40 deep[e[k].to]=deep[x]+1; 41 anc[e[k].to][0]=x; 42 dfs(e[k].to,x); 43 } 44 } 45 int get(int x,int y) 46 { 47 //if(deep[x]<deep[y]) swap(x,y); 48 int t,i,ansx=0,ansy=0,minx=p[x],maxy=p[y]; 49 for(t=deep[x]-deep[y],i=0;t>0;t>>=1,i++) 50 if(t&1) 51 { 52 ansx=max(ansx,max(maxans[x][i],maxn[x][i]-minx)); 53 minx=min(minx,minn[x][i]); 54 x=anc[x][i]; 55 } 56 for(t=deep[y]-deep[x],i=0;t>0;t>>=1,i++) 57 if(t&1) 58 { 59 ansy=max(ansy,max(minans[y][i],maxy-minn[y][i])); 60 maxy=max(maxy,maxn[y][i]); 61 y=anc[y][i]; 62 } 63 if(x==y) 64 return max(max(ansx,ansy),maxy-minx); 65 for(i=log2n;i>=0;i--) 66 if(anc[x][i]!=anc[y][i]) 67 { 68 ansx=max(ansx,max(maxans[x][i],maxn[x][i]-minx)); 69 minx=min(minx,minn[x][i]); 70 ansy=max(ansy,max(minans[y][i],maxy-minn[y][i])); 71 maxy=max(maxy,maxn[y][i]); 72 x=anc[x][i]; 73 y=anc[y][i]; 74 } 75 ansx=max(ansx,max(maxans[x][0],maxn[x][0]-minx)); 76 minx=min(minx,minn[x][0]); 77 ansy=max(ansy,max(minans[y][0],maxy-minn[y][0])); 78 maxy=max(maxy,maxn[y][0]); 79 return max(max(max(ansx,ansy),maxy-minx),max(p[anc[x][0]]-minx,maxy-p[anc[y][0]])); 80 } 81 int main() 82 { 83 int i,t1,t2,a,b; 84 while(scanf("%d",&n)==1) 85 { 86 log2n=log2(n); 87 ne=0;ans1=0; 88 memset(f1,0,sizeof(f1)); 89 memset(minn,0x3f,sizeof(minn)); 90 memset(maxn,0,sizeof(maxn)); 91 memset(minans,0,sizeof(minans)); 92 memset(maxans,0,sizeof(maxans)); 93 for(i=1;i<=n;i++) 94 scanf("%d",&p[i]); 95 scanf("%d",&m); 96 for(i=1;i<=m;i++) 97 scanf("%d%d%d",&e1[i].a,&e1[i].b,&e1[i].w); 98 sort(e1+1,e1+m+1); 99 for(i=1;i<=n;i++) 100 fa[i]=i; 101 for(i=1;i<=m;i++) 102 { 103 t1=find(e1[i].a); 104 t2=find(e1[i].b); 105 if(t1==t2) continue; 106 e[++ne].to=e1[i].b; 107 e[ne].nxt=f1[e1[i].a]; 108 e[ne].d=e1[i].w; 109 f1[e1[i].a]=ne; 110 e[++ne].to=e1[i].a; 111 e[ne].nxt=f1[e1[i].b]; 112 e[ne].d=e1[i].w; 113 f1[e1[i].b]=ne; 114 fa[t1]=t2; 115 ans1+=e1[i].w; 116 } 117 printf("%d\n",ans1); 118 dfs(1,0); 119 scanf("%d",&q); 120 while(q--) 121 { 122 scanf("%d%d",&a,&b); 123 printf("%d\n",get(a,b)); 124 } 125 } 126 return 0; 127 }
