team2012-E1-mysol-0019
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
/* 解题报告 //
给出 n 个点，m 条边，题目要求是先求一个最大生成树
在生成树上，给出 q 次查询，每次询问一条从 x 到 y 的路径
然后求 c[j] - c[i] 的最大值，其中 i 和 j 均是路径上的点
且对于这条路径而言，j 出现的位置不会比 i 出现的位置更靠前
最大生成树的做法就不用说了，大家都会吧？来说说怎么处理查询
首先，你必须要会用倍增法来求 Kaguya's Game 那题的 LCA 查询
如果不会的话，可以去看看那题我的解题报告
然后要维护一些数据，以便之后的查询，要维护的值有这些：
1. 从结点 x 出发，向根走 2 ^ i 步到达的祖先是谁
2. 从结点 x 出发，向根走 2 ^ i 步的这条路径上（含路径起点，不含终点）
2.1. 最小值是多少（此程序里的 lo 数组）
2.2. 最大值是多少（此程序里的 hi 数组）
2.3. 对于路径中间任意的两点 i 和 j，在满足条件 i <= j 的情况下
2.3.1. c[j] - c[i] 的最大值为多少（此程序里的 up 数组）
2.3.2. c[i] - c[j] 的最大值为多少（此程序里的 dn 数组）
由于都是『向根走 2 ^ i 步』的那种类型的数据，所以可以倍增地维护
具体维护方法可以参考 init() 函数
对于查询一条路径 x 到 y，不妨令 w = lca(x, y)
可以发现，x 到 y 这条路径可以被分解成一些长度为 2 ^ i 的段
段的总数是 O(logN) 级别的，最优答案可能来自两个部分：
1. 每段内部
1.1. 对于 x 到 w 的路径，答案来自 up 数组
1.2. 对于 w 到 y 的路径，答案来自 dn 数组（因为路径是反向的）
2. 段与段之间
把每段的最大值和最小值各自拿出来放在两个数组 l 和 h 内
l[i] = 前 i 个数中的最小值，h[i] = 从 i 开始直到末尾这些数中的最大值
再线性地扫一遍，就可以得到答案了
// By 猛犸也钻地 @ 2012.07.26 */
}}}
{{{
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> TPL;
const int INF = 1000000007;
int sz[50000],p[50000],c[50000],lv[50000];
int fa[50000][16],lo[50000][16],hi[50000][16];
int up[50000][16],dn[50000][16];
vector<int> e[50000];
TPL u[50000];
int root(int x){
return p[x]!=x?p[x]=root(p[x]):x;
}
bool join(int x, int y){
x=root(x),y=root(y);
if(x==y) return false;
if(sz[x]<=sz[y]) sz[p[x]=y]+=sz[x];
else sz[p[y]=x]+=sz[y];
return true;
}
void init(int x, int src){
up[x][0]=dn[x][0]=-INF;
lo[x][0]=hi[x][0]=c[x];
fa[x][0]=src;
lv[x]=lv[src]+1;
for(int i=1;i<16;i++){
int r=fa[x][i-1];
fa[x][i]=fa[r][i-1];
lo[x][i]=min(lo[r][i-1],lo[x][i-1]);
hi[x][i]=max(hi[r][i-1],hi[x][i-1]);
up[x][i]=max(hi[r][i-1]-lo[x][i-1],max(up[r][i-1],up[x][i-1]));
dn[x][i]=max(hi[x][i-1]-lo[r][i-1],max(dn[r][i-1],dn[x][i-1]));
}
}
void make_tree(int x, int src){
init(x,src);
for(size_t i=0;i<e[x].size();i++)
if(e[x][i]!=src) make_tree(e[x][i],x);
}
int lca(int x, int y){
int c=lv[x]-lv[y];
if(c>0) for(int i=0;i<16;i++) if(+c&1<<i) x=fa[x][i];
if(c<0) for(int i=0;i<16;i++) if(-c&1<<i) y=fa[y][i];
if(x==y) return x;
for(int i=15;~i;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int gao(int x, int y, int w){
int p=lv[x]-lv[w];
int q=lv[y]-lv[w],ret=0;
vector<int> l,h,L,H;
for(int i=0;i<16;i++){
if(p&1<<i){
ret=max(ret,up[x][i]);
l.push_back(lo[x][i]);
h.push_back(hi[x][i]);
x=fa[x][i];
}
if(q&1<<i){
ret=max(ret,dn[y][i]);
L.push_back(lo[y][i]);
H.push_back(hi[y][i]);
y=fa[y][i];
}
}
l.push_back(c[w]); l.insert(l.end(),L.rbegin(),L.rend());
h.push_back(c[w]); h.insert(h.end(),H.rbegin(),H.rend());
for(size_t i=h.size()-2;~i;i--) h[i]=max(h[i],h[i+1]);
for(size_t i=1;i!=l.size();i++) l[i]=min(l[i],l[i-1]),ret=max(ret,h[i]-l[i-1]);
return ret;
}
int main(){
int n,m,x,y,w;
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++){
scanf("%d",c+i);
sz[p[i]=i]=1;
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
u[i]=TPL(w,PII(x-1,y-1));
}
long long ans=0;
sort(u,u+m);
for(int i=m-1,cnt=1;~i;i--){
x=u[i].second.first;
y=u[i].second.second;
if(!join(x,y)) continue;
ans+=u[i].first;
e[x].push_back(y);
e[y].push_back(x);
if(++cnt==n) break;
}
printf("%lld\n",ans);
make_tree(0,0);
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
w=lca(--x,--y);
printf("%d\n",gao(x,y,w));
}
for(int i=0;i<n;i++) e[i].clear();
}
}
}}}/* 解题报告 //
给出 n 个点，m 条边，题目要求是先求一个最大生成树
在生成树上，给出 q 次查询，每次询问一条从 x 到 y 的路径
然后求 c[j] - c[i] 的最大值，其中 i 和 j 均是路径上的点
且对于这条路径而言，j 出现的位置不会比 i 出现的位置更靠前
最大生成树的做法就不用说了，大家都会吧？来说说怎么处理查询
首先，你必须要会用倍增法来求 Kaguya's Game 那题的 LCA 查询
如果不会的话，可以去看看那题我的解题报告
然后要维护一些数据，以便之后的查询，要维护的值有这些：
1. 从结点 x 出发，向根走 2 ^ i 步到达的祖先是谁
2. 从结点 x 出发，向根走 2 ^ i 步的这条路径上（含路径起点，不含终点）
2.1. 最小值是多少（此程序里的 lo 数组）
2.2. 最大值是多少（此程序里的 hi 数组）
2.3. 对于路径中间任意的两点 i 和 j，在满足条件 i <= j 的情况下
2.3.1. c[j] - c[i] 的最大值为多少（此程序里的 up 数组）
2.3.2. c[i] - c[j] 的最大值为多少（此程序里的 dn 数组）
由于都是『向根走 2 ^ i 步』的那种类型的数据，所以可以倍增地维护
具体维护方法可以参考 init() 函数
对于查询一条路径 x 到 y，不妨令 w = lca(x, y)
可以发现，x 到 y 这条路径可以被分解成一些长度为 2 ^ i 的段
段的总数是 O(logN) 级别的，最优答案可能来自两个部分：
1. 每段内部
1.1. 对于 x 到 w 的路径，答案来自 up 数组
1.2. 对于 w 到 y 的路径，答案来自 dn 数组（因为路径是反向的）
2. 段与段之间
把每段的最大值和最小值各自拿出来放在两个数组 l 和 h 内
l[i] = 前 i 个数中的最小值，h[i] = 从 i 开始直到末尾这些数中的最大值
再线性地扫一遍，就可以得到答案了
// By 猛犸也钻地 @ 2012.07.26 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> TPL;
const int INF = 1000000007;
int sz[50000],p[50000],c[50000],lv[50000];
int fa[50000][16],lo[50000][16],hi[50000][16];
int up[50000][16],dn[50000][16];
vector<int> e[50000];
TPL u[50000];
int root(int x){
return p[x]!=x?p[x]=root(p[x]):x;
}
bool join(int x, int y){
x=root(x),y=root(y);
if(x==y) return false;
if(sz[x]<=sz[y]) sz[p[x]=y]+=sz[x];
else sz[p[y]=x]+=sz[y];
return true;
}
void init(int x, int src){
up[x][0]=dn[x][0]=-INF;
lo[x][0]=hi[x][0]=c[x];
fa[x][0]=src;
lv[x]=lv[src]+1;
for(int i=1;i<16;i++){
int r=fa[x][i-1];
fa[x][i]=fa[r][i-1];
lo[x][i]=min(lo[r][i-1],lo[x][i-1]);
hi[x][i]=max(hi[r][i-1],hi[x][i-1]);
up[x][i]=max(hi[r][i-1]-lo[x][i-1],max(up[r][i-1],up[x][i-1]));
dn[x][i]=max(hi[x][i-1]-lo[r][i-1],max(dn[r][i-1],dn[x][i-1]));
}
}
void make_tree(int x, int src){
init(x,src);
for(size_t i=0;i<e[x].size();i++)
if(e[x][i]!=src) make_tree(e[x][i],x);
}
int lca(int x, int y){
int c=lv[x]-lv[y];
if(c>0) for(int i=0;i<16;i++) if(+c&1<<i) x=fa[x][i];
if(c<0) for(int i=0;i<16;i++) if(-c&1<<i) y=fa[y][i];
if(x==y) return x;
for(int i=15;~i;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int gao(int x, int y, int w){
int p=lv[x]-lv[w];
int q=lv[y]-lv[w],ret=0;
vector<int> l,h,L,H;
for(int i=0;i<16;i++){
if(p&1<<i){
ret=max(ret,up[x][i]);
l.push_back(lo[x][i]);
h.push_back(hi[x][i]);
x=fa[x][i];
}
if(q&1<<i){
ret=max(ret,dn[y][i]);
L.push_back(lo[y][i]);
H.push_back(hi[y][i]);
y=fa[y][i];
}
}
l.push_back(c[w]); l.insert(l.end(),L.rbegin(),L.rend());
h.push_back(c[w]); h.insert(h.end(),H.rbegin(),H.rend());
for(size_t i=h.size()-2;~i;i--) h[i]=max(h[i],h[i+1]);
for(size_t i=1;i!=l.size();i++) l[i]=min(l[i],l[i-1]),ret=max(ret,h[i]-l[i-1]);
return ret;
}
int main(){
int n,m,x,y,w;
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++){
scanf("%d",c+i);
sz[p[i]=i]=1;
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
u[i]=TPL(w,PII(x-1,y-1));
}
long long ans=0;
sort(u,u+m);
for(int i=m-1,cnt=1;~i;i--){
x=u[i].second.first;
y=u[i].second.second;
if(!join(x,y)) continue;
ans+=u[i].first;
e[x].push_back(y);
e[y].push_back(x);
if(++cnt==n) break;
}
printf("%lld\n",ans);
make_tree(0,0);
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
w=lca(--x,--y);
printf("%d\n",gao(x,y,w));
}
for(int i=0;i<n;i++) e[i].clear();
}
}