codevs 3305 水果姐逛水果街Ⅱ

发表于 | 分类于

题目描述

水果姐第二天心情也很不错，又来逛水果街。

突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。

同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。

cgh给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。

水果姐向学过oi的你求助。

输入输出格式

输入格式：

第一行n，表示有n家店

下来n个正整数，表示每家店一个苹果的价格。

下来n-1行，每行两个整数x，y，表示第x家店和第y家店有一条边。

下来一个整数m，表示下来有m个询问。

下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。

输出格式：

有m行。

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

输入输出描述

样例输入:
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
样例输出：
7
11
7
0
0
15

说明

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

0<n<=200000

0<m<=10000

分析

很显然这是一道比较裸的lca
然而我lca倍增并不很熟练
虽然周888大佬告诉我这题也可以用tarjian做
总之维护一堆乱七八糟的值就行

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int Inf=999999999;
int top[202020][28]; 
int maxn[202020][28],minn[202020][28],up[202020][28],down[202020][28];
int pre[404040],now[202020],son[404040];
int v[202020],deep[202020];
int n,m,doe;
inline void read(int &x)
{
    int data=0,w=1;
    char ch=0;
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') w=-1,ch=getchar();
    while (ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
void add(int x,int y)
{
	++doe;
	pre[doe]=now[x];
	now[x]=doe;
	son[doe]=y;
}
int get_lca(int x,int y)
{
	if (deep[x]<deep[y]) swap(x,y);
	int d=deep[x]-deep[y];
	if (d)
	{
		for (int i=20;i>=0;--i)
			if (d&(1<<i))
				x=top[x][i];
	}
	
	if (x!=y) 
		for (int i=20;i>=0;--i)
		if (top[x][i]!=top[y][i])
		{
			x=top[x][i];
			y=top[y][i];
		}
	if (x==y) return x;
	else return top[x][0];
}
	
int ask(int x,int y)
{
	int lca=get_lca(x,y);
	int ans=0,bit=Inf,big=-Inf;
	int d=deep[x]-deep[lca];
	if (d)
		for (int i=20;i>=0;--i)
			if (d&(1<<i))
			{
				ans=max(ans,max( up[x][i] , maxn[x][i]-bit ));
				bit=min(bit,minn[x][i]);
				x=top[x][i]; 	
			}
			
	d=deep[y]-deep[lca];
	if (d)
		for (int i=20;i>=0;--i)
			if (d&(1<<i))
			{
				ans=max(ans,max( down[y][i] , big-minn[y][i] ));
				big=max(big,maxn[y][i]);
				y=top[y][i]; 	
			}
	
	return max(ans,big-bit);
}
void dfs(int x,int fa)
{
	deep[x]=deep[fa]+1;
	top[x][0]=fa;
	maxn[x][0]=max(v[x],v[fa]);
	minn[x][0]=min(v[x],v[fa]);
	up[x][0]=max(0,v[fa]-v[x]);
	down[x][0]=max(0,v[x]-v[fa]);
	
	for (int i=1;i<=20;++i)
	{
		top[x][i]=top[top[x][i-1]][i-1];
		if (!top[x][i]) break;
		int y=top[x][i-1];
		maxn[x][i]=max(maxn[x][i-1],maxn[y][i-1]);
		minn[x][i]=min(minn[x][i-1],minn[y][i-1]);
		up[x][i]=max( max(up[x][i-1],up[y][i-1]) , maxn[y][i-1]-minn[x][i-1] );
		down[x][i]=max( max(down[x][i-1],down[y][i-1]) , maxn[x][i-1]-minn[y][i-1] );
	}
	
	int p=now[x];
	while (p)
	{
		int y=son[p];
		if (y!=fa)
			dfs(y,x);
		p=pre[p];
	}
}
int main(){
	int x,y;
	read(n);
	for (int i=1;i<=n;++i)
		read(v[i]);
	for (int i=1;i<n;++i)
	{
		read(x); read(y);
		add(x,y);
		add(y,x);
	}
	
	dfs(1,0);
	
	read(m);
	for (int i=1;i<=m;++i)
	{
		read(x); read(y);
		printf("%d\n",ask(x,y));
	}		
	return 0;
}
--------------------------