2012-A3-0019
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题目大意:一张带有边权和点权的图，要从这个图求一个net,题目保证这个net唯一,这个net要用最少的边数，然后还要最大的边权和，似乎还要保证所有点联通.
于是大概是个最大生成树，然后给出若干询问，从X走到Y（不走回头路），按顺序经过的点权，先选个小的，再选个大的，使大的和小的的差最大，
如果点权依次递减或平，根据样例则是输出0.
那么就先根据题意求个MaximumSpanningTree，
树上的路径是唯一的，于是在无根树里任选个点作为根，使之成为一个有根树，询问X到Y的路径，就是询问XY的LCA，
路径就是X->LCA(X,Y)->Y.然后可以在建立有根树和求LCA的过程维护一些域
z到某个祖先的路径上的答案，那个祖先到z的路径上的答案，这条路径上的点权最大值，和最小值.
然后如果已经求出，z到某个祖先A(z)的上述域,和A(z)到它的某祖先A（A(z)）的上述域，就可以通过二者求出z 到A(A(z))的上述域.
可以倍增求出2^k^次阶祖先，然后在log,,2,,n的复杂度里合并路径求出到任意祖先的上述域.
然后通过求LCA，在合并求出的路径得出最后的答案
x到y，的答案就是 MAX{(x到LCA(x,y)的答案),(LCA(x,y)到y的答案)，（LCA到y上的最大值-x到LCA(x,y)的最小值)}
{{{
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef unsigned u32;
#define go(i,n) for(u32 i=0;i<(n);++i)
pair<u32,u32> ed[51200];
vector<u32> e[32768];
u32 f[32768],r[32768];
u32 ff(u32 x){return x!=f[x]?f[x]=ff(f[x]):x;}
struct {u32 ac;int x,y,mx,mn;}o[30000][16];
void dfs(u32 u,u32 uf){
f[u]=f[uf]+1;
u32 ac=o[u][0].ac=uf;
o[u][0].mx=max(r[u],r[ac]);
o[u][0].mn=min(r[u],r[ac]);
o[u][0].x=max(0,(int)(r[ac]-r[u]));
o[u][0].y=max(0,(int)(r[u]-r[ac]));
go(i,14){
o[u][i+1].mx=max(o[ac][i].mx,o[u][i].mx);
o[u][i+1].mn=min(o[ac][i].mn,o[u][i].mn);
o[u][i+1].x=max(max(o[u][i].x,o[ac][i].x),o[ac][i].mx-o[u][i].mn);
o[u][i+1].y=max(max(o[u][i].y,o[ac][i].y),o[u][i].mx-o[ac][i].mn);
ac=o[u][i+1].ac=o[ac][i].ac;
}
go(i,e[u].size())if(e[u][i]!=uf)
dfs(e[u][i],u);
}
int main(){
srand(time(0));
for(u32 n,m,a,b,c,mst;scanf("%u",&n)==1;){
go(i,n)scanf("%u",r+i);
scanf("%u",&m);
go(i,m){
scanf("%u%u%u",&a,&b,&c);
ed[i]= make_pair(-c,--a<<16|--b);
}
go(i,n){f[i]=i;e[i].clear();}
sort(ed,ed+m);mst=0;
go(i,m)
if(ff(a=ed[i].second>>16)!=ff(b=ed[i].second&65535)){
e[a].push_back(b);
e[b].push_back(a);
mst-=ed[i].first;
f[ff(b)]=ff(a);
}
printf("%u\n",mst);
f[c = rand()%n]=0;//printf("root==%u\n",c);
dfs(c,c);
scanf("%u",&m);
for(int mx,mn,as;m--;printf("%d\n",max(as,mx-mn))){
scanf("%u%u",&a,&b);
mn=r[--a];mx=r[--b];as=0;
for(u32 t;f[a]>f[b];a=o[a][t].ac){
t=__builtin_ctz(f[b]-f[a]);
as = max(as,max(o[a][t].x,o[a][t].mx-mn));
mn = min(mn,o[a][t].mn);
}
for(u32 t;f[b]>f[a];b=o[b][t].ac){
t=__builtin_ctz(f[a]-f[b]);
as = max(as,max(o[b][t].y,mx-o[b][t].mn));
mx = max(mx,o[b][t].mx);
}
if(a!=b){
for(u32 i=15;i--;)
if(o[a][i].ac!=o[b][i].ac){
as=max(as,max(max(o[a][i].mx-mn,mx-o[b][i].mn),max(o[a][i].x,o[b][i].y)));
mn=min(mn,o[a][i].mn);
mx=max(mx,o[b][i].mx);
a=o[a][i].ac;b=o[b][i].ac;
}
as=max(as,max(o[a][0].x,o[b][0].y));
mn=min(mn,o[a][0].mn);
mx=max(mx,o[b][0].mx);
}
}
}
}
}}}题目大意:一张带有边权和点权的图，要从这个图求一个net,题目保证这个net唯一,这个net要用最少的边数，然后还要最大的边权和，似乎还要保证所有点联通.
于是大概是个最大生成树，然后给出若干询问，从X走到Y（不走回头路），按顺序经过的点权，先选个小的，再选个大的，使大的和小的的差最大，
如果点权依次递减或平，根据样例则是输出0.
那么就先根据题意求个MaximumSpanningTree，
树上的路径是唯一的，于是在无根树里任选个点作为根，使之成为一个有根树，询问X到Y的路径，就是询问XY的LCA，
路径就是X->LCA(X,Y)->Y.然后可以在建立有根树和求LCA的过程维护一些域
z到某个祖先的路径上的答案，那个祖先到z的路径上的答案，这条路径上的点权最大值，和最小值.
然后如果已经求出，z到某个祖先A(z)的上述域,和A(z)到它的某祖先A（A(z)）的上述域，就可以通过二者求出z 到A(A(z))的上述域.
可以倍增求出2k次阶祖先，然后在log2n的复杂度里合并路径求出到任意祖先的上述域.
然后通过求LCA，在合并求出的路径得出最后的答案
x到y，的答案就是 MAX{(x到LCA(x,y)的答案),(LCA(x,y)到y的答案)，（LCA到y上的最大值-x到LCA(x,y)的最小值)}
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef unsigned u32;
#define go(i,n) for(u32 i=0;i<(n);++i)
pair<u32,u32> ed[51200];
vector<u32> e[32768];
u32 f[32768],r[32768];
u32 ff(u32 x){return x!=f[x]?f[x]=ff(f[x]):x;}
struct {u32 ac;int x,y,mx,mn;}o[30000][16];
void dfs(u32 u,u32 uf){
f[u]=f[uf]+1;
u32 ac=o[u][0].ac=uf;
o[u][0].mx=max(r[u],r[ac]);
o[u][0].mn=min(r[u],r[ac]);
o[u][0].x=max(0,(int)(r[ac]-r[u]));
o[u][0].y=max(0,(int)(r[u]-r[ac]));
go(i,14){
o[u][i+1].mx=max(o[ac][i].mx,o[u][i].mx);
o[u][i+1].mn=min(o[ac][i].mn,o[u][i].mn);
o[u][i+1].x=max(max(o[u][i].x,o[ac][i].x),o[ac][i].mx-o[u][i].mn);
o[u][i+1].y=max(max(o[u][i].y,o[ac][i].y),o[u][i].mx-o[ac][i].mn);
ac=o[u][i+1].ac=o[ac][i].ac;
}
go(i,e[u].size())if(e[u][i]!=uf)
dfs(e[u][i],u);
}
int main(){
srand(time(0));
for(u32 n,m,a,b,c,mst;scanf("%u",&n)==1;){
go(i,n)scanf("%u",r+i);
scanf("%u",&m);
go(i,m){
scanf("%u%u%u",&a,&b,&c);
ed[i]= make_pair(-c,--a<<16|--b);
}
go(i,n){f[i]=i;e[i].clear();}
sort(ed,ed+m);mst=0;
go(i,m)
if(ff(a=ed[i].second>>16)!=ff(b=ed[i].second&65535)){
e[a].push_back(b);
e[b].push_back(a);
mst-=ed[i].first;
f[ff(b)]=ff(a);
}
printf("%u\n",mst);
f[c = rand()%n]=0;//printf("root==%u\n",c);
dfs(c,c);
scanf("%u",&m);
for(int mx,mn,as;m--;printf("%d\n",max(as,mx-mn))){
scanf("%u%u",&a,&b);
mn=r[--a];mx=r[--b];as=0;
for(u32 t;f[a]>f[b];a=o[a][t].ac){
t=__builtin_ctz(f[b]-f[a]);
as = max(as,max(o[a][t].x,o[a][t].mx-mn));
mn = min(mn,o[a][t].mn);
}
for(u32 t;f[b]>f[a];b=o[b][t].ac){
t=__builtin_ctz(f[a]-f[b]);
as = max(as,max(o[b][t].y,mx-o[b][t].mn));
mx = max(mx,o[b][t].mx);
}
if(a!=b){
for(u32 i=15;i--;)
if(o[a][i].ac!=o[b][i].ac){
as=max(as,max(max(o[a][i].mx-mn,mx-o[b][i].mn),max(o[a][i].x,o[b][i].y)));
mn=min(mn,o[a][i].mn);
mx=max(mx,o[b][i].mx);
a=o[a][i].ac;b=o[b][i].ac;
}
as=max(as,max(o[a][0].x,o[b][0].y));
mn=min(mn,o[a][0].mn);
mx=max(mx,o[b][0].mx);
}
}
}
}