Social Net ZOJ - 3649
题意：
反正原题题意我是看不懂...
参考：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.html ?1 #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 }Social Net ZOJ - 3649
原文地址：http://www.cnblogs.com/hehe54321/p/zoj-3649.html