poj 3728(LCA)

发表于 | 分类于 | | + s

poj 3728

维护6个数组
pre[i][j] i的第2^j个祖先
deep[i] i的深度
up[i][j] i到i的第2^j个祖先的最优解
down[i][j] i的第2^j个祖先到i的最优解
dmax[i][j] i到i的第2^j个祖先路径上的最大值
dmin[i][j] i到i的第2^j个祖先路径上的最小值
然后可以通过倍增维护以上数组，期中包含一些dp思想，此题非常好，作为一个LCA的跳板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj3728" 
using namespace std;

const int ZINF2 = 100000000, MAXN = 50000 + 5, logs = 16;

int n, wi[MAXN],
 pre[MAXN][logs+1], deep[MAXN], up[MAXN][logs+1], down[MAXN][logs+1], dmax[MAXN][logs+1], dmin[MAXN][logs+1];
 /*维护6个数组 
     pre[i][j] i的第2^j个祖先
      deep[i] i的深度
    up[i][j] i到i的第2^j个祖先的最优解
    down[i][j] i的第2^j个祖先到i的最优解
    dmax[i][j] i到i的第2^j个祖先路径上的最大值
    dmin[i][j] i到i的第2^j个祖先路径上的最小值
 */
vector<int> G[MAXN];

void dfs(int x, int p)
{
    pre[x][0] = p;
    deep[x] = deep[p] + 1;
    dmax[x][0] = max(wi[x], wi[p]);
    dmin[x][0] = min(wi[x], wi[p]);
    up[x][0] = max(0, wi[p]-wi[x]);
    down[x][0] = max(0, wi[x]-wi[p]);
    for (int i=1;i<=logs;i++)
    {
        int pa = pre[x][i-1];
        pre[x][i] = pre[pa][i-1];
        dmax[x][i] = max(dmax[pa][i-1], dmax[x][i-1]);
        dmin[x][i] = min(dmin[pa][i-1], dmin[x][i-1]);
        up[x][i] = max(up[pa][i-1], up[x][i-1]);//合并 
        up[x][i] = max(up[x][i], dmax[pa][i-1]-dmin[x][i-1]); 
        down[x][i] = max(down[pa][i-1], down[x][i-1]);//合并
        down[x][i] = max(down[x][i], dmax[x][i-1]-dmin[pa][i-1]); 
    }
    for (int i=0;i<G[x].size();i++)
    {
        int v = G[x][i];
        if (p!=v)
        {
            dfs(v, x);
        }
    }
}
int lca(int a, int b)
{
    if (deep[a]>deep[b]) swap(a, b);
    for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i];
    if (a==b) return a;
    for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}
void climb(int x, int y, bool UP, int &ans, int &temp)
{
    temp = wi[x];
    int del = deep[x] - deep[y];
    for (int i=logs;i>=0;i--)
    {
        if ((del>>i) & 1)
        {
            if (UP)
            {
                ans = max(ans, dmax[x][i] - temp);//有可能不在up里
                temp = min(temp, dmin[x][i]);
                ans = max(ans, up[x][i]);
            } else 
            {
                ans = max(ans, temp - dmin[x][i]);
                temp = max(temp, dmax[x][i]);
                ans = max(ans, down[x][i]);
            }
            x = pre[x][i];
        }
    }
}
void init()
{
    for (int i=1;i<=n;i++)
    {
        deep[i] = 0;
        for (int j=0;j<=logs;j++) pre[i][j] = 0;
        scanf("%d", &wi[i]);
    }
    for (int i=1;i<n;i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y), G[y].push_back(x);
    }
}
void solve()
{
    dfs(1, 0);
    int q;
    scanf("%d" ,&q);
    for (int i=1;i<=q;i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int px, py, ans = 0, lc = lca(x, y);
        climb(x, lc, 1, ans, px); climb(y, lc, 0, ans, py);
        printf("%d\n", max(ans, py - px));
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen(FN2".in","r",stdin);
    freopen(FN2".out","w",stdout);
    #endif
    while (scanf("%d", &n)==1)
    {
        init();
        solve();
    }
    return 0;
}
------ 本文结束 ------