【-71】3305 水果姐逛水果街Ⅱ[倍增LCA]

2017-08-31

题目描述 Description

水果姐第二天心情也很不错，又来逛水果街。突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。同样还是n家水果店，编号为 $1$ ~ $n$ ，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。cgh给出 $m$ 个问题，每个问题要求水果姐从第 $x$ 家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店 （可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。水果姐向学过oi的你求助。

输入描述 Input Description

第一行 $n$ ，表示有n家店下来 $n$ 个正整数，表示每家店一个苹果的价格。下来 $n-1$ 行，每行两个整数 $x，y$ ，表示第 $x$ 家店和第 $y$ 家店有一条边。下来一个整数 $m$ ，表示下来有 $m$ 个询问。下来有 $m$ 行，每行两个整数 $x$ 和 $y$ ，表示从第 $x$ 家店出发到第 $y$ 家店。

输出描述 Output Description

有 $m$ 行。每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。

样例输入 Sample Input

10
16 5 1 15 15 1 8 9 9 15 
1 2
1 3
2 4
2 5
2 6
6 7
4 8
1 9
1 10
6
9 1
5 1
1 7
3 3
1 1
3 6

样例输出 Sample Output7

数据范围及提示 Data Size & Hint

$0<=苹果的价格<=10^8$

$0<n<=200000$

$0<m<=10000$

题解

这道题简直有毒.

因为不能往回走,所以单纯的维护 $max$ 和 $min$ 是不够的.

还需要维护两个 $ans$ ,一个是从这个节点往根节点走的 $ans$ ,另一个是从根节点往这个节点走的 $ans$ .

在更新 $ans$ 的时候,有多种情况

某一部分的ans
如果是从 $x->lca(x,y)$ 的 $ans$ , 可以下面部分取 $min$ ,上面部分取 $max$ 进行更新
如果是从 $lca(x,y)->y$ 的 $ans$ ,可以在下面部分取 $max$ , 上面部分取 $min$ 进行更新
然后可以 $x->lca(x,y)$ 取 $min$ , $lca(x,y)->y$ 取 $max$ 进行更新
然后不要忘记用他们的最近公共祖先更新 $min$ 和 $max$

嗯表述很奇怪,具体看代码,代码还是很好懂的

#include<bits/stdc++.h>
using namespace std;
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9')
    {
        k=k*10+(s-'0');
        s=getchar();
    }
    return k*base;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        write(-x);
    }
    else
    {
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
}
const int maxn=200010;
int n,Q;//点的个数,询问个数
int a[maxn];//点权
int f[30][maxn];//存父亲
int m[30][maxn];//max
int s[30][maxn];//min
int ans1[30][maxn];//往上走到根的ans
int ans2[30][maxn];//从根往下走的ans
int to[maxn*2];//链式前向星
int ne[maxn*2];
int po[maxn];
int de[maxn];
int maxde,Log;//记录最大深度,要搜多少
int lb;
int X,Y;
inline void add(int x,int y)//加边
{
    lb++;to[lb]=y;ne[lb]=po[x];po[x]=lb;
}
inline void dfs(int x)
{
    maxde=max(maxde,de[x]);//更新最大深度
    for (int i=po[x];i;i=ne[i])
    {
        if (f[0][x]!=to[i])//如果这条边连的不是父亲
        {
            int xx=to[i];
            f[0][xx]=x;//xx的父亲是x
            m[0][xx]=max(a[x],a[xx]);//更新max
            s[0][xx]=min(a[x],a[xx]);//更新min
            ans1[0][xx]=max(0,-a[xx]+a[x]);//更新ans1,往上走就是减去自己的点权+父亲的点权
            ans2[0][xx]=max(0,-a[x]+a[xx]);//更新ans2
            de[xx]=de[x]+1;//记录深度
            dfs(xx);//往下扫
        }
    }
}
inline int find(int x,int y)//x->y
{
    int ans=0;
    int Max=a[y];//存终点到lca的max
    int Min=2333333;//存起点到lca的min
    if (de[x]>de[y])//使2者深度相同,因为起点和终点不能换位置
    {//所以判断,分开搞
        for (int i=0;i<Log;i++)
        {
            if ((de[x]-de[y])>>i & 1)//de[x]-de[y]转成二进制后第i位如果为1就要往上移那么多
            {
                ans=max(ans,ans1[i][x]);
                ans=max(ans,-Min+m[i][x]);//更新ans,之后才能更新min(因为min更新之后就包括x~x+2^i那一部分,就会gg)
                Min=min(Min,s[i][x]);//更新min
                x=f[i][x];//更新x,这个要最后更新
            }
        }
    } else 
    if (de[x]<de[y])
    {
        for (int i=0;i<Log;i++)
        {
            if ((de[y]-de[x])>>i & 1)
            {
                ans=max(ans,ans2[i][y]);
                ans=max(ans,Max-s[i][y]);
                Max=max(Max,m[i][y]);//更新Max,同理
                y=f[i][y];
            }
        }
    }
    for (int i=Log-1;i>=0;i--)
    {
        if (f[i][x]!=f[i][y]&&f[i][x]!=-1&&f[i][y]!=-1)
        {//如果往上跳2^i次方祖先不同就网上跳
            ans=max(ans,ans1[i][x]);//更新ans
            ans=max(ans,-Min+m[i][x]);//更新ans,然后更新min
            Min=min(Min,s[i][x]);//更新min
          
            ans=max(ans,ans2[i][y]);//更新ans
            ans=max(ans,Max-s[i][y]);
            Max=max(Max,m[i][y]);//更新min
            x=f[i][x];//往上跳
            y=f[i][y];
        }
    }//所以我不知道我为何要这个奇怪的特判
    if (x!=y&&f[0][x]!=-1) Min=min(Min,s[0][x]);//然后还要更新一次,因为可以在
    if (x!=y&&f[0][y]!=-1) Max=max(Max,m[0][y]);//他们lca的地方进行交易
    //某些奇怪的判断(什么if(x!=y)是我倍增的bug,我也不知道为什么)
    ans=max(ans,Max-Min);
    return ans;
}
int main()
{    
    n=read();
    memset(f,-1,sizeof(f));
    for (int i=1;i<=n;i++) a[i]=read();//读入点权
    for (int i=1;i<n;i++)
    {
        X=read();Y=read();
        add(X,Y);add(Y,X);//加边
    }
    m[0][1]=a[1];s[0][1]=a[1];de[1]=1;
    dfs(1);//预处理
    while (maxde)
    {
        maxde/=2;
        Log++;
    }
    for (int i=1;i<Log;i++)
        for (int j=1;j<=n;j++)
        {//求点j的2^i祖先
            if (j==1) continue;//1为根节点,不需要往上扫了
            if (f[i-1][j]==-1) continue;//没有第2^(i-1)个祖先也不用扫了
            f[i][j]=f[i-1][f[i-1][j]];
            //j的2^i祖先=j的2^(i-1)个祖先的2^(i-1)个祖先
            if (f[i][j]==-1) continue;//没有2^i祖先也不用更新了
            m[i][j]=max(m[i-1][j],m[i-1][f[i-1][j]]);//更新max
            s[i][j]=min(s[i-1][j],s[i-1][f[i-1][j]]);//更新min
            ans1[i][j]=max(ans1[i-1][j],ans1[i-1][f[i-1][j]]);//更新ans
            ans1[i][j]=max(ans1[i][j],-s[i-1][j]+m[i-1][f[i-1][j]]);
            ans2[i][j]=max(ans2[i-1][j],ans2[i-1][f[i-1][j]]);
            ans2[i][j]=max(ans2[i][j],m[i-1][j]-s[i-1][f[i-1][j]]);
        }
    Q=read();
    while (Q--)
    {
        X=read();Y=read();
        if (X==Y) //特判掉
        {
            printf("0\n");
            continue;
        }
        printf("%d\n",find(X,Y));//从x->y,输出
    }
    return 0;
}