这题是吴老师推荐的，于是我就去做了。
根据题意，在完成最大生成树后，对于树上从x到y的一条路径，求出最大的ck-cj(j<=k,ci为路径上第i个点的权值)。
我一开始的想法是二分，记路径xy的中点是mid，路径ab的答案记为ans(a,b)，最大值为mx(a,b)，最小值为mn(a,b)，那么，ans(x,y)=max{ans(x,mid),ans(y,mid),mx(mid,y)-mn(x,mid)}。
但我忘记了一个问题，对于时间复杂度T(n)=2T(n/2)+logn，由主定理可知，解为T(n)=O(n)。换言之这并没有比暴力优越。
然而，正如同求路径上的最大最小值一样，我们可以通过倍增的方法把ans预处理出来，然后在O(logn)的时间内得到解。
具体说就是把一个点向上2^i的答案和一个点第2^i-1个祖先到i的答案都预处理出来。而预处理和最终计算答案的方法和上述的二分是完全一致的。
所以，我们可以通过O(n*logn)的时间完成预处理，再对与每个询问O(logn)地得到解。
时间复杂度O(n*logn+q*logn)。
?1 #include <bits/stdc++.h> ?2 using namespace std; ?3 template <typename tp> inline void read(tp& x) ?4 { ?5 ????x=0; ?6 ????char tmp=getchar();bool key=0; ?7 ????for(;!((tmp>=‘0‘&&tmp<=‘9‘)||tmp==‘-‘);) tmp=getchar(); ?8 ????if(tmp==‘-‘) key=1,tmp=getchar(); ?9 ????for(;tmp>=‘0‘&&tmp<=‘9‘;) x=(x<<1)+(x<<3)+tmp-‘0‘,tmp=getchar(); 10 ????if(key) x=-x; 11 } 12 const int N=30010,M=50010,MAXPOS=15; 13 struct edge_for_buildtree{ 14 ????int a,b,v; 15 ????bool operator < (const edge_for_buildtree& x)const 16 ????{ 17 ????????return v>x.v; 18 ????} 19 }ed[M]; 20 struct edge_for_lca{ 21 ????int la,b; 22 }con[N<<1]; 23 int tot,fir[N]; 24 inline void add(int from,int to) 25 { 26 ????con[++tot].la=fir[from]; 27 ????con[tot].b=to; 28 ????fir[from]=tot; 29 } 30 int n,m,q,val[N],flag[N],anc[N][MAXPOS+5],mn[N][MAXPOS+5],mx[N][MAXPOS+5],deep[N]; 31 int recu[N][MAXPOS+5],recd[N][MAXPOS+5]; 32 inline void init() 33 { 34 ????memset(anc,0,sizeof anc); 35 ????memset(mn,0x3f,sizeof mn); 36 ????memset(mx,0,sizeof mx); 37 ????memset(fir,0,sizeof fir); 38 ????memset(recu,0,sizeof recu); 39 ????memset(recd,0,sizeof recd); 40 ????tot=0; 41 } 42 int get_flag(int pos) 43 { 44 ????return flag[pos]==pos? pos : flag[pos]=get_flag(flag[pos]); 45 } 46 inline void kruskal() 47 { 48 ????int x,y,ans=0,cnt=0; 49 ????sort(ed+1,ed+m+1); 50 ????for(register int i=1;i<=n;++i) flag[i]=i; 51 ????for(register int i=1;i<=m;++i) 52 ????{ 53 ????????x=ed[i].a;y=ed[i].b; 54 ????????x=get_flag(x);y=get_flag(y); 55 ????????if(x==y) continue; 56 ????????add(ed[i].a,ed[i].b); 57 ????????add(ed[i].b,ed[i].a); 58 ????????ans+=ed[i].v; 59 ????????flag[x]=y; 60 ????????if(++cnt==n-1) break; 61 ????} 62 ????printf("%d\n",ans); 63 } 64 void dfs_init(int pos) 65 { 66 ????deep[pos]=deep[anc[pos][0]]+1; 67 ????mn[pos][0]=mx[pos][0]=val[pos]; 68 ????recu[pos][0]=recd[pos][0]=0; 69 ????for(int i=1;i<=MAXPOS;++i) 70 ????{ 71 ????????anc[pos][i]=anc[anc[pos][i-1]][i-1]; 72 ????????mn[pos][i]=min(mn[pos][i-1],mn[anc[pos][i-1]][i-1]); 73 ????????mx[pos][i]=max(mx[pos][i-1],mx[anc[pos][i-1]][i-1]); 74 ????????recu[pos][i]=max(max(recu[pos][i-1],recu[anc[pos][i-1]][i-1]),mx[anc[pos][i-1]][i-1]-mn[pos][i-1]); 75 ????????recd[pos][i]=max(max(recd[pos][i-1],recd[anc[pos][i-1]][i-1]),mx[pos][i-1]-mn[anc[pos][i-1]][i-1]); 76 ????????if(anc[pos][i]==0) break; 77 ????} 78 ????for(int i=fir[pos];i;i=con[i].la) 79 ????{ 80 ????????if(con[i].b==anc[pos][0]) continue; 81 ????????anc[con[i].b][0]=pos; 82 ????????dfs_init(con[i].b); 83 ????} 84 } 85 inline int lca(int x,int y) 86 { 87 ????if(deep[x]<deep[y]) swap(x,y); 88 ????for(int i=MAXPOS;i>=0;--i) 89 ????{ 90 ????????if(deep[anc[x][i]]>=deep[y]) x=anc[x][i]; 91 ????} 92 ????if(x==y) return x; 93 ????for(int i=MAXPOS;i>=0;--i) 94 ????{ 95 ????????if(anc[x][i]!=anc[y][i]) 96 ????????????x=anc[x][i],y=anc[y][i]; 97 ????} 98 ????return anc[x][0]; 99 }100 inline int get_mn(int x,int y)//y is the ancestor of x101 {102 ????if(x==y) return val[x];103 ????int res=val[x],len=deep[x]-deep[y]+1;104 ????for(int i=MAXPOS;i>=0;--i)105 ????{106 ????????if(len>=(1<<i))107 ????????????res=min(res,mn[x][i]),x=anc[x][i],len-=(1<<i);108 ????}109 ????return res;110 }111 inline int get_mx(int x,int y)//y is the ancestor of x112 {113 ????if(x==y) return val[x];114 ????int res=val[x],len=deep[x]-deep[y]+1;115 ????for(int i=MAXPOS;i>=0;--i)116 ????{117 ????????if(len>=(1<<i))118 ????????????res=max(res,mx[x][i]),x=anc[x][i],len-=(1<<i);119 ????}120 ????return res;121 }122 inline int ask_mn(int x,int y,int lc)123 {124 ????return min(get_mn(x,lc),get_mn(y,lc));125 }126 inline int ask_mx(int x,int y,int lc)127 {128 ????return max(get_mx(x,lc),get_mx(y,lc));129 }130 inline int get_recu(int x,int y)//y is the ancestor of x131 {132 ????if(x==y) return 0;133 ????int mnpre=1000000,res=0;134 ????for(int i=MAXPOS;i>=0;i--)135 ????{136 ????????if(deep[anc[x][i]]>=deep[y])137 ????????{138 ????????????res=max(res,recu[x][i]);139 ????????????res=max(res,mx[x][i]-mnpre);140 ????????????mnpre=min(mnpre,mn[x][i]);141 ????????????x=anc[x][i];142 ????????}143 ????}144 ????return res;145 }146 inline int get_recd(int x,int y)147 {148 ????if(x==y) return 0;149 ????int mxpre=0,res=0;150 ????for(int i=MAXPOS;i>=0;i--)151 ????{152 ????????if(deep[anc[x][i]]>=deep[y])153 ????????{154 ????????????res=max(res,recd[x][i]);155 ????????????res=max(res,mxpre-mn[x][i]);156 ????????????mxpre=max(mxpre,mx[x][i]);157 ????????????x=anc[x][i];158 ????????}159 ????}160 ????return res;161 }162 inline int solve(int x,int y)163 {164 ????if(x==y) return 0;165 ????if(anc[x][0]==y||anc[y][0]==x) return max(0,val[y]-val[x]);166 ????int z=lca(x,y);167 ????int res=max(get_recu(x,z),get_recd(y,z));168 ????res=max(res,ask_mx(y,z,z)-ask_mn(x,z,z));169 ????return res;170 }171 int main()172 {173 ????int x,y,v;174 ????while(scanf("%d",&n)!=EOF)175 ????{176 ????????init();177 ????????for(register int i=1;i<=n;++i) read(val[i]);178 ????????read(m);179 ????????for(register int i=1;i<=m;++i)180 ????????{181 ????????????read(x);read(y);read(v);182 ????????????ed[i]=(edge_for_buildtree){x,y,v};183 ????????}184 ????????kruskal();185 ????????dfs_init(1);186 ????????read(q);187 ????????for(;q--;)188 ????????{189 ????????????read(x);read(y);190 ????????????printf("%d\n",solve(x,y));191 ????????}192 ????}193 ????return 0;194 }小结：通常对于无修改的题目，这种看似无用的二分往往可以通过倍增来优化。
【做题】zoj3649 Social Net——倍增
原文地址：http://www.cnblogs.com/cly-none/p/7749576.html