这题是吴老师推荐的,于是我就去做了。

根据题意,在完成最大生成树后,对于树上从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)。

 #include <bits/stdc++.h>
using namespace std;
template <typename tp> inline void read(tp& x)
{
x=;
char tmp=getchar();bool key=;
for(;!((tmp>=''&&tmp<='')||tmp=='-');) tmp=getchar();
if(tmp=='-') key=,tmp=getchar();
for(;tmp>=''&&tmp<='';) x=(x<<)+(x<<)+tmp-'',tmp=getchar();
if(key) x=-x;
}
const int N=,M=,MAXPOS=;
struct edge_for_buildtree{
int a,b,v;
bool operator < (const edge_for_buildtree& x)const
{
return v>x.v;
}
}ed[M];
struct edge_for_lca{
int la,b;
}con[N<<];
int tot,fir[N];
inline void add(int from,int to)
{
con[++tot].la=fir[from];
con[tot].b=to;
fir[from]=tot;
}
int n,m,q,val[N],flag[N],anc[N][MAXPOS+],mn[N][MAXPOS+],mx[N][MAXPOS+],deep[N];
int recu[N][MAXPOS+],recd[N][MAXPOS+];
inline void init()
{
memset(anc,,sizeof anc);
memset(mn,0x3f,sizeof mn);
memset(mx,,sizeof mx);
memset(fir,,sizeof fir);
memset(recu,,sizeof recu);
memset(recd,,sizeof recd);
tot=;
}
int get_flag(int pos)
{
return flag[pos]==pos? pos : flag[pos]=get_flag(flag[pos]);
}
inline void kruskal()
{
int x,y,ans=,cnt=;
sort(ed+,ed+m+);
for(register int i=;i<=n;++i) flag[i]=i;
for(register int i=;i<=m;++i)
{
x=ed[i].a;y=ed[i].b;
x=get_flag(x);y=get_flag(y);
if(x==y) continue;
add(ed[i].a,ed[i].b);
add(ed[i].b,ed[i].a);
ans+=ed[i].v;
flag[x]=y;
if(++cnt==n-) break;
}
printf("%d\n",ans);
}
void dfs_init(int pos)
{
deep[pos]=deep[anc[pos][]]+;
mn[pos][]=mx[pos][]=val[pos];
recu[pos][]=recd[pos][]=;
for(int i=;i<=MAXPOS;++i)
{
anc[pos][i]=anc[anc[pos][i-]][i-];
mn[pos][i]=min(mn[pos][i-],mn[anc[pos][i-]][i-]);
mx[pos][i]=max(mx[pos][i-],mx[anc[pos][i-]][i-]);
recu[pos][i]=max(max(recu[pos][i-],recu[anc[pos][i-]][i-]),mx[anc[pos][i-]][i-]-mn[pos][i-]);
recd[pos][i]=max(max(recd[pos][i-],recd[anc[pos][i-]][i-]),mx[pos][i-]-mn[anc[pos][i-]][i-]);
if(anc[pos][i]==) break;
}
for(int i=fir[pos];i;i=con[i].la)
{
if(con[i].b==anc[pos][]) continue;
anc[con[i].b][]=pos;
dfs_init(con[i].b);
}
}
inline int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=MAXPOS;i>=;--i)
{
if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
}
if(x==y) return x;
for(int i=MAXPOS;i>=;--i)
{
if(anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i];
}
return anc[x][];
}
inline int get_mn(int x,int y)//y is the ancestor of x
{
if(x==y) return val[x];
int res=val[x],len=deep[x]-deep[y]+;
for(int i=MAXPOS;i>=;--i)
{
if(len>=(<<i))
res=min(res,mn[x][i]),x=anc[x][i],len-=(<<i);
}
return res;
}
inline int get_mx(int x,int y)//y is the ancestor of x
{
if(x==y) return val[x];
int res=val[x],len=deep[x]-deep[y]+;
for(int i=MAXPOS;i>=;--i)
{
if(len>=(<<i))
res=max(res,mx[x][i]),x=anc[x][i],len-=(<<i);
}
return res;
}
inline int ask_mn(int x,int y,int lc)
{
return min(get_mn(x,lc),get_mn(y,lc));
}
inline int ask_mx(int x,int y,int lc)
{
return max(get_mx(x,lc),get_mx(y,lc));
}
inline int get_recu(int x,int y)//y is the ancestor of x
{
if(x==y) return ;
int mnpre=,res=;
for(int i=MAXPOS;i>=;i--)
{
if(deep[anc[x][i]]>=deep[y])
{
res=max(res,recu[x][i]);
res=max(res,mx[x][i]-mnpre);
mnpre=min(mnpre,mn[x][i]);
x=anc[x][i];
}
}
return res;
}
inline int get_recd(int x,int y)
{
if(x==y) return ;
int mxpre=,res=;
for(int i=MAXPOS;i>=;i--)
{
if(deep[anc[x][i]]>=deep[y])
{
res=max(res,recd[x][i]);
res=max(res,mxpre-mn[x][i]);
mxpre=max(mxpre,mx[x][i]);
x=anc[x][i];
}
}
return res;
}
inline int solve(int x,int y)
{
if(x==y) return ;
if(anc[x][]==y||anc[y][]==x) return max(,val[y]-val[x]);
int z=lca(x,y);
int res=max(get_recu(x,z),get_recd(y,z));
res=max(res,ask_mx(y,z,z)-ask_mn(x,z,z));
return res;
}
int main()
{
int x,y,v;
while(scanf("%d",&n)!=EOF)
{
init();
for(register int i=;i<=n;++i) read(val[i]);
read(m);
for(register int i=;i<=m;++i)
{
read(x);read(y);read(v);
ed[i]=(edge_for_buildtree){x,y,v};
}
kruskal();
dfs_init();
read(q);
for(;q--;)
{
read(x);read(y);
printf("%d\n",solve(x,y));
}
}
return ;
}

小结:通常对于无修改的题目,这种看似无用的二分往往可以通过倍增来优化。

最新文章

  1. iOS 后台处理
  2. angularJs 控制文本长度,超出省略号过滤器
  3. Neutron 理解 (9): OpenStack 是如何实现 Neutron 网络 和 Nova虚机 防火墙的 [How Nova Implements Security Group and How Neutron Implements Virtual Firewall]
  4. Java 数组基础
  5. Mysql常见四种索引的使用
  6. paip.注册java程序为LINUX系统服务的总结。
  7. A new start
  8. Python--Cmd窗口运行Python时提示Fatal Python error: Py_Initialize: can&#39;t initialize sys standard streams LookupError: unknown encoding: cp65001
  9. myeclipse10安装egit和使用
  10. C++里的int 和string类型相互转换
  11. 解决Twitter Bootstrap Tab URL链接问题
  12. hdu4010 Query On The Trees
  13. WCF-IIS-PDA
  14. iOS中点击背景收键盘
  15. npm install安装时忘记--save解决方法
  16. vs2017 asp.net 网站发布问题 (发布路径下含源码文件)
  17. Linux如何查看机器的配置信息
  18. HDU 1010生成树
  19. SQL 游标 Cursor 基本用法
  20. JSP指示元素&lt;%@ %&gt; 与指示类型

热门文章

  1. JavaScript(六):错误处理机制
  2. 记一次CentOS5.7更新glibc导致libc.so.6失效,系统无法启动
  3. html5-移动端布局模板
  4. Linux 运维测试及第三应用及测试工具
  5. linux centos重置mysql密码教程
  6. Spark学习之路 (十五)SparkCore的源码解读(一)启动脚本
  7. ESB(Enterprise Service Bus)企业服务总线介绍
  8. go语言,golang学习笔记3 用命令下载框架报错问题解决 设置环境变量
  9. Lucene 个人领悟 (二)
  10. AtCoder Beginner Contest 044 B - 美しい文字列 / Beautiful Strings