Codevs 3305 水果姐逛水果街Ⅱ 倍增LCA-白红宇

Codevs 3305 水果姐逛水果街Ⅱ 倍增LCA

阅读量：6991 次

发布时间：2019-06-27

本文共 5384 字，大约阅读时间需要 17 分钟。

题目:

时间限制: 2 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述

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

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

9 1

5 1

1 7

3 3

1 1

3 6

样例输出

Sample Output

数据范围及提示

Data Size & Hint

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

0<n<=200000

0<m<=10000

题解：

和3304同理，改为树上倍增即可。

处理信息特别麻烦。。。

代码略丑。。。

1 #include
          
             2 using namespace std;  3 #define MAXN 200010  4 #define INF 1e9  5 struct node  6 {  7     int begin,end,next;  8 }edge[MAXN*2];  9 int cnt,Head[MAXN],n,P[MAXN][18],mx[MAXN][18],mn[MAXN][18],lc[MAXN][18],rc[MAXN][18],deep[MAXN],a[MAXN]; 10 bool vis[MAXN]; 11 void addedge(int bb,int ee) 12 { 13     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt; 14 } 15 void addedge1(int bb,int ee) 16 { 17     addedge(bb,ee);addedge(ee,bb); 18 } 19 int read() 20 { 21     int s=0,fh=1;char ch=getchar(); 22     while(ch<'0'||ch>'9'){
        if(ch=='-')fh=-1;ch=getchar();} 23     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();} 24     return s*fh; 25 } 26 void dfs1(int u) 27 { 28     int i,j,v; 29     vis[u]=true; 30     for(j=1;(1<
           
            <=n;j++) 31     { 32         P[u][j]=P[P[u][j-1]][j-1]; 33         mx[u][j]=max(mx[u][j-1],mx[P[u][j-1]][j-1]); 34         mn[u][j]=min(mn[u][j-1],mn[P[u][j-1]][j-1]); 35         lc[u][j]=max(lc[u][j-1],lc[P[u][j-1]][j-1]); 36         lc[u][j]=max(lc[u][j],mx[P[u][j-1]][j-1]-mn[u][j-1]); 37         rc[u][j]=max(rc[u][j-1],rc[P[u][j-1]][j-1]); 38         rc[u][j]=max(rc[u][j],mx[u][j-1]-mn[P[u][j-1]][j-1]); 39     } 40     for(i=Head[u];i!=-1;i=edge[i].next) 41     { 42         v=edge[i].end; 43         if(vis[v]==false) 44         { 45             deep[v]=deep[u]+1; 46             P[v][0]=u; 47             mx[v][0]=max(a[u],a[v]);//最大值 48             mn[v][0]=min(a[u],a[v]);//最小值 49             lc[v][0]=max(0,a[u]-a[v]);//从i点到达fa[i][j]点的最大利润. 50             rc[v][0]=max(0,a[v]-a[u]);//从fa[i][j]点到达i点的最大利润. 51             dfs1(v); 52         } 53     } 54 } 55 /*void Ycl() 56 { 57     int i,j; 58     for(j=1;(1<
            
             <=n;j++) 59     { 60         for(i=1;i<=n;i++) 61         { 62             if(P[i][j-1]!=-1) 63             { 64                 P[i][j]=P[P[i][j-1]][j-1]; 65                 mx[i][j]=max(mx[i][j],max(mx[i][j-1],mx[P[i][j-1]][j-1])); 66                 mn[i][j]=min(mn[i][j],min(mn[i][j-1],mn[P[i][j-1]][j-1])); 67                 lc[i][j]=max(lc[i][j],max(lc[i][j-1],lc[P[i][j-1]][j-1])); 68                 lc[i][j]=max(lc[i][j],mx[P[i][j-1]][j-1]-mn[i][j-1]); 69                 rc[i][j]=max(rc[i][j],max(rc[i][j-1],rc[P[i][j-1]][j-1])); 70                 rc[i][j]=max(rc[i][j],mx[i][j-1]-mn[P[i][j-1]][j-1]); 71             } 72         } 73     } 74 }*/ 75 int LCA(int x,int y) 76 { 77     int i,j; 78     if(deep[x]
             
              =0;j--)if(deep[x]-(1<
              
               =deep[y])x=P[x][j]; 81     if(x==y)return x; 82     for(j=i;j>=0;j--) 83     { 84         if(P[x][j]!=-1&&P[x][j]!=P[y][j]) 85         { 86             x=P[x][j]; 87             y=P[y][j]; 88         } 89     } 90     return P[x][0]; 91 } 92 int MAX1(int x,int y) 93 { 94     int i,j,maxv=-INF; 95     if(deep[x]
               
                =0;j--) 98 { 99 if(deep[x]-(1<
                
                 =deep[y])100 {101 maxv=max(maxv,lc[x][j]);102 x=P[x][j];103 }104 }105 return maxv;106 }107 int MAX2(int x,int y)108 {109 int i,j,maxv=-INF;110 if(deep[x]
                 
                  =0;j--)113 {114 if(deep[x]-(1<
                  
                   =deep[y])115 {116 maxv=max(maxv,rc[x][j]);117 x=P[x][j];118 }119 }120 return maxv;121 }122 int MX(int x,int y)123 {124 int i,j,maxv=-INF;125 if(deep[x]
                   
                    =0;j--)128 {129 if(deep[x]-(1<
                    
                     =deep[y])130 {131 maxv=max(maxv,mx[x][j]);132 x=P[x][j];133 }134 }135 return maxv;136 }137 int MN(int x,int y)138 {139 int i,j,minv=INF;140 if(deep[x]
                     
                      =0;j--)143 {144 if(deep[x]-(1<
                      
                       =deep[y])145 {146 minv=min(minv,mn[x][j]);147 x=P[x][j];148 }149 }150 return minv;151 }152 int Ask(int x,int y)153 {154 int lca=LCA(x,y),xx=x,yy=y,i,j;155 int maxxx=-INF,minnn=INF,ans=0;156 if(deep[x]
                       
                        =0;j--)159 {160 if(deep[x]-(1<
                        
                         =deep[lca])161 {162 ans=max(ans,max(lc[x][j],mx[x][j]-minnn));163 minnn=min(mn[x][j],minnn);164 x=P[x][j];165 }166 }167 if(deep[y]
                         
                          =0;j--)170 {171 if(deep[y]-(1<
                          
                           =deep[lca])172 {173 ans=max(ans,max(rc[y][j],maxxx-mn[y][j]));174 maxxx=max(mx[y][j],maxxx);175 y=P[y][j];176 }177 }178 return max(ans,maxxx-minnn);179 }180 int main()181 {182 int bb,ee,i,j,m,x,y,ans,lca;183 n=read();184 for(i=1;i<=n;i++)a[i]=read();185 memset(Head,-1,sizeof(Head));cnt=1;186 for(i=1;i
                           
                            y)swap(x,y);210 /*lca=LCA(x,y);211 ans=0;212 ans=max(ans,MAX1(x,lca));213 ans=max(ans,MAX2(lca,y));214 ans=max(ans,MX(lca,y)-MN(x,lca));215 printf("%d\n",ans);*/216 }217 /*else218 {219 lca=LCA(x,y);220 ans=-INF;221 ans=max(ans,MAX1(x,lca));222 ans=max(ans,MAX2(y,lca));223 ans=max(ans,MX(y,lca)-MN(x,lca));224 printf("%d\n",ans);225 }*/226 }227 return 0;228 }