水果姐逛水果街Ⅱ codevs 3305

3305 水果姐逛水果街Ⅱ

时间限制: 2 s

空间限制: 256000 KB

题目描述 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 Output

7
11
7
0
0
15

数据范围及提示 Data Size & Hint

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

0<n<=200000

0<m<=10000

用f[i][j]表示i往上2^j的祖先。

mx[i][j]表示i到f[i][j]的最大值

mi[i][j]表示i到f[i][j]的最小值

fr[i][j]表示f[i][j]到i的最大获利

to[i][j]表示i到f[i][j]的最大获利

递推方程：

f[i][j]=f[f[i][j-1]][j-1];

mx[i][j]=max(mx[i][j-1],mx[f[i][j-1]][j-1]);

mi[i][j]=max(mi[i][j-1],mi[f[i][j-1]][j-1]);

fr[i][j]=max(fr[i][j-1],fr[f[i][j-1][j-1],mx[f[i][j-1]][j-1]-mi[i][j-1]);

to[i][j]=max(to[i][j-1],to[f[i][j-1]][j-1],mx[i][j-1]-mi[f[i][j-1]][j-1]);

1,2,3不解释，4,5：对于从f[i][j]到i的最大值有可能在f[i][j-1]到i或f[i][j]到f[i][j-1]这一段或分别在这两段，两个类同。

所以对于树上两点u,v的最大获益有三种可能：

1.在u到lca(u,v);

2.在v到lca(u,v）;

3.在1买入，在2售出;

所以求解时只需要在u,v分别往上跳即可.

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=,INF=1e9;

struct X

{

    int v,f,n;

}x[N<<];

int sale[N],s,dep[N],f[N][],mx[N][],mi[N][],fr[N][],to[N][];

int read()

{

    char c;

    while((c=getchar())<''||c>'');

    int re=c-'';

    while((c=getchar())>=''&&c<='') re=(re<<)+(re<<)+c-'';

    return re;

}

void add(int u,int v)

{

    x[++s].n=x[u].f;

    x[x[u].f=s].v=v;

}

void dfs(int u,int fa)

{

    dep[u]=dep[f[u][]=fa]+;

    mx[u][]=max(sale[u],sale[fa]);

    mi[u][]=min(sale[u],sale[fa]);

    fr[u][]=sale[u]-sale[fa];

    to[u][]=-fr[u][];

    for(int i=;i<;i++)

    {

        f[u][i]=f[f[u][i-]][i-];

        mx[u][i]=max(mx[f[u][i-]][i-],mx[u][i-]);

        mi[u][i]=min(mi[f[u][i-]][i-],mi[u][i-]);

        fr[u][i]=max(max(fr[f[u][i-]][i-],fr[u][i-]),mx[u][i-]-mi[f[u][i-]][i-]);

        to[u][i]=max(max(to[f[u][i-]][i-],to[u][i-]),mx[f[u][i-]][i-]-mi[u][i-]);

    }

    for(int i=x[u].f;i;i=x[i].n)

        if(x[i].v!=fa) dfs(x[i].v,u);

}

int lca(int u,int v)

{

    if(dep[u]<dep[v]) swap(u,v);

    int dlt=dep[u]-dep[v];

    for(int i=;i<;i++)

        if(dlt>>i&) u=f[u][i];

    if(u==v) return v;

    for(int i=;i>=;i--)

        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];

    return f[u][];

}

int main()

{

    int n=read();

    for(int i=;i<=n;i++) sale[i]=read();

    while(--n)

    {

        int u=read(),v=read();

        add(u,v);add(v,u);

    }

    dfs(,);

    n=read();

    while(n--)

    {

        int u=read(),v=read(),fath=lca(u,v),dlt=dep[u]-dep[fath],maxx=-INF,minn=INF,ans=;

        if(dlt)//从u跳

            for(int i=;i<;i++)

                if(dlt>>i&)

                {

                    ans=max(ans,max(to[u][i],mx[u][i]-minn));

                    minn=min(minn,mi[u][i]);

                    u=f[u][i];

                }

        dlt=dep[v]-dep[fath];

        if(dlt)//从v跳

            for(int i=;i<;i++)

                if(dlt>>i&)

                {

                    ans=max(ans,max(fr[v][i],maxx-mi[v][i]));

                    maxx=max(maxx,mx[v][i]);

                    v=f[v][i];

                }

        ans=max(maxx-minn,ans);//用历史最大与历史最小相减

        printf("%d\n",ans);

    }

    return ;

}

巴特西

水果姐逛水果街Ⅱ codevs 3305

3305 水果姐逛水果街Ⅱ

最新文章

热门文章