team2012-F3-sol-0019
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
题意：首先给定一个图要求出最大生成树，然后在这个树上进行多个询问，每个询问形如(a, b)
要回答的是一个最大差值 d = v[i] - v[j]，其中 i 和 j 是 a 到 b 路径上的点，且 i 的出现顺序后于 j
解法：
通过修改求LCA的倍增法可以解决这个题，首先除了记录 x 向上走 2^i 步的祖先 fa[x][i] 外，还要记录
up[x][i] : 这一段上从 x 走到那个祖先可以获得的最大差值，为 max { up[fa[x][i-1]][i-1], up[x][i-1], mx[fa[x][i-1]][i-1] - mi[x][i-1] }
dn[x][i] : 这一段上从那个祖先走到 x 可以获得的最大差值，类似上面
mx[x][i] : 这一段上的最大值
mi[x][i] : 这一段上的最小值
然后对于每个询问，求LCA的同时，记录下所有这些经过的段，那么答案为三种方式获得的差值中的最大值，具体为：
max{ max{ up[x][i] | 所有从 a 到 LCA 经过的段 },
max{ dn[x][i] | 所有从 LCA 到 b 经过的段 },
max{ mx[第i段] - mi[第j段] | j < i } }
}}}
{{{
#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 30003, MAXM = 50005, MAXDP = 16;
vector<int> conn[MAXN];
int f[MAXN], v[MAXN], n, m, q, fa[MAXN][MAXDP], dp[MAXN];
int mx[MAXN][MAXDP], mi[MAXN][MAXDP], up[MAXN][MAXDP], dn[MAXN][MAXDP];
struct edge
{
int a, b, l;
friend bool operator<(const edge& a, const edge& b)
{
return a.l > b.l;
}
}e[MAXM];
int getf(int x)
{
if(x == f[x]) return x;
return f[x] = getf(f[x]);
}
int mst()
{
sort(e+1, e+m+1);
for(int i = 1; i <= n; i++)
f[i] = i, conn[i].clear();
int ret = 0;
for(int i = 1; i <= m; i++)
{
int fa = getf(e[i].a), fb = getf(e[i].b);
if(fa != fb)
{
f[fa] = fb;
ret += e[i].l;
conn[e[i].a].push_back(e[i].b);
conn[e[i].b].push_back(e[i].a);
}
}
return ret;
}
void dfs(int x)
{
dp[x] = dp[f[x]] + 1;
fa[x][0] = f[x];
if(f[x] == 0)
{
mx[x][0] = mi[x][0] = v[x];
up[x][0] = dn[x][0] = 0;
}
else
{
mx[x][0] = max(v[x], v[f[x]]);
mi[x][0] = min(v[x], v[f[x]]);
up[x][0] = max(v[f[x]] - v[x], 0);
dn[x][0] = max(v[x] - v[f[x]], 0);
}
for(int i = 1; i < MAXDP; i++)
{
up[x][i] = max(up[fa[x][i-1]][i-1], max(up[x][i-1], mx[fa[x][i-1]][i-1] - mi[x][i-1]));
dn[x][i] = max(dn[fa[x][i-1]][i-1], max(dn[x][i-1], mx[x][i-1] - mi[fa[x][i-1]][i-1]));
mi[x][i] = min(mi[x][i-1], mi[fa[x][i-1]][i-1]);
mx[x][i] = max(mx[x][i-1], mx[fa[x][i-1]][i-1]);
fa[x][i] = fa[fa[x][i-1]][i-1];
}
for(int i = 0; i < conn[x].size(); i++)
{
int u = conn[x][i];
if(u != f[x])
{
f[u] = x;
dfs(u);
}
}
}
int gao_lca(int a, int b)
{
int det = 0;
vector<int> max_arr1, min_arr1, max_arr2, min_arr2;
if(dp[a] > dp[b])
{
int d = dp[a] - dp[b];
for(int i = 0; i < MAXDP; i++)
if(d & (1<<i))
{
takemax(det, up[a][i]);
max_arr1.push_back(mx[a][i]);
min_arr1.push_back(mi[a][i]);
a = fa[a][i];
}
}
else if(dp[a] < dp[b])
{
int d = dp[b] - dp[a];
for(int i = 0; i < MAXDP; i++)
if(d & (1<<i))
{
takemax(det, dn[b][i]);
max_arr2.push_back(mx[b][i]);
min_arr2.push_back(mi[b][i]);
b = fa[b][i];
}
}
if(a != b)
{
for(int i = MAXDP-1; i >= 0; i--)
if(fa[a][i] != fa[b][i])
{
takemax(det, up[a][i]), takemax(det, dn[b][i]);
max_arr1.push_back(mx[a][i]), min_arr1.push_back(mi[a][i]);
max_arr2.push_back(mx[b][i]), min_arr2.push_back(mi[b][i]);
a = fa[a][i], b = fa[b][i];
}
takemax(det, up[a][0]), takemax(det, dn[b][0]);
max_arr1.push_back(mx[a][0]), min_arr1.push_back(mi[a][0]);
max_arr2.push_back(mx[b][0]), min_arr2.push_back(mi[b][0]);
}
for(int i = max_arr2.size()-1; i >= 0; i--)
max_arr1.push_back(max_arr2[i]), min_arr1.push_back(min_arr2[i]);
for(int i = 1; i < min_arr1.size(); i++)
min_arr1[i] = min(min_arr1[i-1], min_arr1[i]);
for(int i = max_arr1.size()-2; i >= 0; i--)
max_arr1[i] = max(max_arr1[i+1], max_arr1[i]);
for(int i = 1; i < max_arr1.size(); i++)
takemax(det, max(0, max_arr1[i] - min_arr1[i-1]));
return det;
}
int main()
{
srand(time(NULL));
while(~scanf("%d", &n))
{
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
scanf("%d", &m);
for(int i = 1; i <= m; i++)
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].l);
printf("%d\n", mst());
int root = rand() % n + 1;
f[root] = 0;
dp[0] = -1;
for(int i = 0; i < MAXDP; i++)
fa[root][i] = 0;
dfs(root);
scanf("%d", &q);
for(int i = 1; i <= q; i++)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", gao_lca(a, b));
}
}
return 0;
}
}}}题意：首先给定一个图要求出最大生成树，然后在这个树上进行多个询问，每个询问形如(a, b)
要回答的是一个最大差值 d = v[i] - v[j]，其中 i 和 j 是 a 到 b 路径上的点，且 i 的出现顺序后于 j
解法：
通过修改求LCA的倍增法可以解决这个题，首先除了记录 x 向上走 2^i 步的祖先 fa[x][i] 外，还要记录
up[x][i] : 这一段上从 x 走到那个祖先可以获得的最大差值，为 max { up[fa[x][i-1]][i-1], up[x][i-1], mx[fa[x][i-1]][i-1] - mi[x][i-1] }
dn[x][i] : 这一段上从那个祖先走到 x 可以获得的最大差值，类似上面
mx[x][i] : 这一段上的最大值
mi[x][i] : 这一段上的最小值
然后对于每个询问，求LCA的同时，记录下所有这些经过的段，那么答案为三种方式获得的差值中的最大值，具体为：
max{ max{ up[x][i] | 所有从 a 到 LCA 经过的段 },
max{ dn[x][i] | 所有从 LCA 到 b 经过的段 },
max{ mx[第i段] - mi[第j段] | j < i } }
#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
template<class T> bool takemin(T& a, T b) {bool Z=(a>b); if(Z)a=b; return Z;}
template<class T> bool takemax(T& a, T b) {bool Z=(a<b); if(Z)a=b; return Z;}
const int MAXN = 30003, MAXM = 50005, MAXDP = 16;
vector<int> conn[MAXN];
int f[MAXN], v[MAXN], n, m, q, fa[MAXN][MAXDP], dp[MAXN];
int mx[MAXN][MAXDP], mi[MAXN][MAXDP], up[MAXN][MAXDP], dn[MAXN][MAXDP];
struct edge
{
int a, b, l;
friend bool operator<(const edge& a, const edge& b)
{
return a.l > b.l;
}
}e[MAXM];
int getf(int x)
{
if(x == f[x]) return x;
return f[x] = getf(f[x]);
}
int mst()
{
sort(e+1, e+m+1);
for(int i = 1; i <= n; i++)
f[i] = i, conn[i].clear();
int ret = 0;
for(int i = 1; i <= m; i++)
{
int fa = getf(e[i].a), fb = getf(e[i].b);
if(fa != fb)
{
f[fa] = fb;
ret += e[i].l;
conn[e[i].a].push_back(e[i].b);
conn[e[i].b].push_back(e[i].a);
}
}
return ret;
}
void dfs(int x)
{
dp[x] = dp[f[x]] + 1;
fa[x][0] = f[x];
if(f[x] == 0)
{
mx[x][0] = mi[x][0] = v[x];
up[x][0] = dn[x][0] = 0;
}
else
{
mx[x][0] = max(v[x], v[f[x]]);
mi[x][0] = min(v[x], v[f[x]]);
up[x][0] = max(v[f[x]] - v[x], 0);
dn[x][0] = max(v[x] - v[f[x]], 0);
}
for(int i = 1; i < MAXDP; i++)
{
up[x][i] = max(up[fa[x][i-1]][i-1], max(up[x][i-1], mx[fa[x][i-1]][i-1] - mi[x][i-1]));
dn[x][i] = max(dn[fa[x][i-1]][i-1], max(dn[x][i-1], mx[x][i-1] - mi[fa[x][i-1]][i-1]));
mi[x][i] = min(mi[x][i-1], mi[fa[x][i-1]][i-1]);
mx[x][i] = max(mx[x][i-1], mx[fa[x][i-1]][i-1]);
fa[x][i] = fa[fa[x][i-1]][i-1];
}
for(int i = 0; i < conn[x].size(); i++)
{
int u = conn[x][i];
if(u != f[x])
{
f[u] = x;
dfs(u);
}
}
}
int gao_lca(int a, int b)
{
int det = 0;
vector<int> max_arr1, min_arr1, max_arr2, min_arr2;
if(dp[a] > dp[b])
{
int d = dp[a] - dp[b];
for(int i = 0; i < MAXDP; i++)
if(d & (1<<i))
{
takemax(det, up[a][i]);
max_arr1.push_back(mx[a][i]);
min_arr1.push_back(mi[a][i]);
a = fa[a][i];
}
}
else if(dp[a] < dp[b])
{
int d = dp[b] - dp[a];
for(int i = 0; i < MAXDP; i++)
if(d & (1<<i))
{
takemax(det, dn[b][i]);
max_arr2.push_back(mx[b][i]);
min_arr2.push_back(mi[b][i]);
b = fa[b][i];
}
}
if(a != b)
{
for(int i = MAXDP-1; i >= 0; i--)
if(fa[a][i] != fa[b][i])
{
takemax(det, up[a][i]), takemax(det, dn[b][i]);
max_arr1.push_back(mx[a][i]), min_arr1.push_back(mi[a][i]);
max_arr2.push_back(mx[b][i]), min_arr2.push_back(mi[b][i]);
a = fa[a][i], b = fa[b][i];
}
takemax(det, up[a][0]), takemax(det, dn[b][0]);
max_arr1.push_back(mx[a][0]), min_arr1.push_back(mi[a][0]);
max_arr2.push_back(mx[b][0]), min_arr2.push_back(mi[b][0]);
}
for(int i = max_arr2.size()-1; i >= 0; i--)
max_arr1.push_back(max_arr2[i]), min_arr1.push_back(min_arr2[i]);
for(int i = 1; i < min_arr1.size(); i++)
min_arr1[i] = min(min_arr1[i-1], min_arr1[i]);
for(int i = max_arr1.size()-2; i >= 0; i--)
max_arr1[i] = max(max_arr1[i+1], max_arr1[i]);
for(int i = 1; i < max_arr1.size(); i++)
takemax(det, max(0, max_arr1[i] - min_arr1[i-1]));
return det;
}
int main()
{
srand(time(NULL));
while(~scanf("%d", &n))
{
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
scanf("%d", &m);
for(int i = 1; i <= m; i++)
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].l);
printf("%d\n", mst());
int root = rand() % n + 1;
f[root] = 0;
dp[0] = -1;
for(int i = 0; i < MAXDP; i++)
fa[root][i] = 0;
dfs(root);
scanf("%d", &q);
for(int i = 1; i <= q; i++)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", gao_lca(a, b));
}
}
return 0;
}