Reincarnation

正因为梦易碎，才格外美好。

CSP-S 2022 题解

发表于 更新于 分类于
本文字数： 21k 阅读时长 ≈ 19 分钟

比较有意思的图论签到题，被吊锤。
场上唯一会做的题。

“不可以，总司令。”

得分甚至高于 。

假期计划

因为有一个特殊条件在于，只需要经过 个权值最大的结点即可，并没有要求经过一个变量的结点，或许这是我们做这道题的突破口。

考虑到这 个点之间的距离都不能超过 ，然后时空复杂度支持 ，可以预处理出两两结点之间的距离。

然后发现 ，都不是太可过的样子，然后发现这个图的所有边权都是 ，可以用 次 解决。（其实也可以用 来着）

然后考虑一种暴力 直接枚举四个到达的点，然后判断即可，可以得到 的好成绩。

然后考虑如何优化到 ，即我们枚举其中两个点，另外两个点根据其依赖关系得到。

然后应该可以知道的是，当我们固定了 之后， 比较好固定：考虑对于每一个点预处理出满足的点集 是有 的结点。但是发现我们这样依赖出的点集可能会重，然后最后计算出来的话，大概对于每一个点记录最大值，次大值，亚大值的话，可以保证凑出一个四维点对 。

然后时间复杂度 ，可过。要开 long long 才能过民间数据。

AC 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// ----- Eternally question-----
// Problem: P8817 [CSP-S 2022] 假期计划
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8817
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2022-11-11 19:01:33
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2.5e3+10,MAXM=1e4+10;
const int INF=0x3f3f3f3f;
int N,M,K;
ll Val[MAXN];
struct G
{
	int next,to;
}Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dist[MAXN][MAXN];
bool Vis[MAXN];
void Bfs(int st)
{
	queue<int>Q;
	Q.push(st);
	for(int i=1;i<=N;++i) Vis[i]=0,Dist[st][i]=INF;
	Dist[st][st]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		if(Vis[x]) continue;
		Vis[x]=1;
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			checkMin(Dist[st][v],Dist[st][x]+1);
			if(!Vis[v]) Q.push(v);
		}
	}
}
bitset<MAXN>Bt[MAXN],Temp,Unit;
struct Node
{
	ll val[3],id[3];
	inline void init(){ val[0]=val[1]=val[2]=id[0]=id[1]=id[2]=0; }
	inline void upDate(ll v,int i)
	{
		if(v>val[0])
		{
			val[2]=val[1],val[1]=val[0],val[0]=v;
			id[2]=id[1],id[1]=id[0],id[0]=i;
		}
		else if(v>val[1])
		{
			val[2]=val[1],val[1]=v;
			id[2]=id[1],id[1]=i;
		}
		else if(v>val[2])
			val[2]=v,id[2]=i;
	}
	inline void print()
	{
		write("val:",val[0],' ',val[1],' ',val[2],'\n');
		write("id: ",id[0],' ',id[1],' ',id[2],'\n');
	}
}Cst[MAXN];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,M,K),Val[1]=0,++K;
	for(int i=2;i<=N;++i) read(Val[i]);
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);addEdge(u,v);
	}
	for(int i=1;i<=N;++i) Bfs(i),Cst[i].init();
	// for(int i=1;i<=N;++i,puts(""))
		 // for(int j=1;j<=N;++j) write(Dist[i][j],' ');
	// for(int i=1;i<=N;++i)
		// for(int j=1;j<=N;++j)
			// if(Dist[i][j]<=K) Bt[i]|=(1<<j),Bt[j]|=(1<<i);
	// for(int i=1;i<=N;++i) std::cout<<Bt[i]<<'\n';
	// Unit.reset();
	// Unit.set(1,true);
	for(int i=2;i<=N;++i)
		for(int j=2;j<=N;++j)
		{
			if(i==j) continue;
			if(Dist[1][j]<=K&&Dist[i][j]<=K) Cst[i].upDate(Val[j],j);
		}
	ll res=-INF;
	// for(int i=2;i<=N;++i) Cst[i].print();
	for(int b=2;b<=N;++b)
		for(int c=2;c<=N;++c)
			for(int a=0;a<3;++a)
				for(int d=0;d<3;++d)
				{
					if(b==c) continue;
					if(Dist[b][c]>K) continue;
					if(!Cst[b].id[a]||!Cst[c].id[d]) continue;
					if(Cst[b].id[a]==Cst[c].id[d]) continue;
					if(Cst[b].id[a]==c||Cst[c].id[d]==b) continue;
					checkMax(res,Val[b]+Val[c]+Cst[b].val[a]+Cst[c].val[d]);
				}
	write(res);
	return 0;
}
/*

*/

策略游戏

考虑到最后会得到一个 的矩阵，（看到两个人玩游戏以为是啥博弈论什么的）但是有 我们不可能真正把这个矩阵构造出来，然后发现，它的询问格式是两个区间（用 表示），然后就会发现合法集合实际上是 ，然后双方都要求的是极值，可能是最小值或者最大值，就可以转化成 问题，用线段树或者 表维护即可（不带修改）。

用线段树维护以下信息：正数最大值，正数最小值，负数最大值，负数最小值。

用 分别表示最大值和最小值，用 来表示正数和负数。

这样的话，我们可以如下讨论：

  • 先后手都只有正数可选，「先手最大正数」乘以「后手最小正数」为答案；
  • 先后手都只有负数可选，「先手最小负数」乘以「后手最大负数」为答案；
  • 先后手只有正负中的一种可选，但不同，答案为「先手绝对值最小的」和「后手绝对值最大的」；
  • 否则的话，就是「先手最小正数」乘以「后手最小负数」和「先手最大负数」乘以「后手最大正数」的最大值 。

口胡极其容易，但是改考场上的大样例 的时候着实需要一些时间，因为会发现有一些问题无法避免：

首先我们需要考虑当前得到的区间是否是合法区间，或者是自己给出的 ，以及应当考虑 的出现情况：我在考场上进行了特判，后来 爷有一种更简洁的方法——把 既当作正数又当作负数，这样是显然正确的。

然后就是特判非法了，可以用两个 bool 变量存储正数负数是否出现过。

测出来的话，如果没有特判 而导致答案错误， 可得 ， 可得 ，当然，避免的方法在于 ，但这样会爆 long long ，用 __int128_t 可以通过。

AC 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// ----- Eternally question-----
// Problem: P8817 [CSP-S 2022] 假期计划
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8818
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2022-11-12 11:10:31
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
const int INF=2e9;
int N,M,Q;
int a[MAXN],b[MAXN];
struct Node
{
	int lp,rp,ln,rn;
	inline void print(){ printf("[%d,%d:%d,%d]\n",ln,rn,lp,rp); }
};
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct ST
	{
		int l,r;
		ll maxpos,minneg,minpos,maxneg;
		bool pos,neg;
	}Tr[MAXN<<2];
	struct Ans
	{
		bool pos,neg;
		ll lp,rp,ln,rn;
		inline void init()
		{
			pos=neg=0;
			lp=ln=INF,rp=rn=-INF;
		}
	};
	inline void upDate(Ans &a,Ans b)
	{
		a.pos|=b.pos,a.neg|=b.neg;
		checkMin(a.lp,b.lp),checkMax(a.rp,b.rp);
		checkMin(a.ln,b.ln),checkMax(a.rn,b.rn);
	}
	inline void pushUp(int p)
	{
		Tr[p].maxpos=std::max(Tr[ls].maxpos,Tr[rs].maxpos);
		Tr[p].minneg=std::min(Tr[ls].minneg,Tr[rs].minneg);
		Tr[p].maxneg=std::max(Tr[ls].maxneg,Tr[rs].maxneg);
		Tr[p].minpos=std::min(Tr[ls].minpos,Tr[rs].minpos);
		Tr[p].pos=Tr[ls].pos|Tr[rs].pos,Tr[p].neg=Tr[ls].neg|Tr[rs].neg;
	}
	void build(int p,int l,int r,int s[])
	{
		Tr[p].l=l,Tr[p].r=r;
		Tr[p].maxpos=-INF,Tr[p].minneg=INF;
		Tr[p].maxneg=-INF,Tr[p].minpos=INF;
		if(l==r)
		{
			if(s[l]<=0) Tr[p].maxneg=Tr[p].minneg=s[l],Tr[p].neg=1;
			if(s[l]>=0) Tr[p].maxpos=Tr[p].minpos=s[l],Tr[p].pos=1;
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid,s),build(rs,mid+1,r,s);
		pushUp(p);
	}
	Ans queryAll(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r)
			return (Ans){Tr[p].pos,Tr[p].neg,Tr[p].minpos,Tr[p].maxpos,Tr[p].minneg,Tr[p].maxneg};
		int mid=(Tr[p].l+Tr[p].r)>>1;Ans res;res.init();
		if(l<=mid) upDate(res,queryAll(ls,l,r));
		if(mid<r) upDate(res,queryAll(rs,l,r));
		return res;
	}
	inline Node querySegment(int l,int r)
	{
		Ans res=queryAll(1,l,r);
		if(!res.neg) return (Node){res.lp,res.rp,1,1};
		if(!res.pos) return (Node){-1,-1,res.ln,res.rn};
		return {res.lp,res.rp,res.ln,res.rn};
	}
	#undef ls
	#undef rs
}TrA,TrB;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,M,Q);
	for(int i=1;i<=N;++i) read(a[i]);
	for(int i=1;i<=M;++i) read(b[i]);
	TrA.build(1,1,N,a),TrB.build(1,1,M,b);
	for(int la,lb,ra,rb;Q--;)
	{
		ll ans;
		read(la,ra,lb,rb);
		Node sega=TrA.querySegment(la,ra),segb=TrB.querySegment(lb,rb);
		// sega.print(),segb.print();
		if(sega.lp==-1&&segb.lp==-1) write(ans=1ll*sega.ln*segb.rn,'\n');
		else if(sega.ln==1&&segb.ln==1) write(ans=1ll*sega.rp*segb.lp,'\n');
		else if(sega.lp==-1) write(ans=1ll*sega.rn*segb.rp,'\n');
		else if(sega.ln==1) write(ans=1ll*sega.lp*segb.ln,'\n');
		else if(segb.lp==-1) write(ans=1ll*sega.ln*segb.rn,'\n');
		else if(segb.ln==1) write(ans=1ll*sega.rp*segb.lp,'\n');
		else write(ans=std::max(1ll*sega.rn*segb.rp,1ll*sega.lp*segb.ln),'\n');
		// if(ans==604255) sega.print(),segb.print();
	}
	return 0;
}
/*

*/

星战

这是一个性质极其优美的图：每个结点有且仅有一条出边，每个结点一定属于某一个环。总的来讲，这个图实际上是一个简单环集。

维护出边很好考虑，可以直接维护 数组，然后考虑如何维护环点包含关系。因为考前一直在复习连通性这一块的，怒码 判断每一个点是否属于某一个大小大于 的强连通分量。

喜提爆蛋。

然后我们说过这个图的性质极其优美，就会发现：如果每一个结点都有出边的话，那它一定会在某一个环中（因为没有自环），正确性显然。

那么，现在就有了一个 的做法：每一次暴力维护数组 ，用 的时间判断。修改的时间复杂度不计，因为一个结点至多修改 条边。

喜提多少咱也不造。

然后不知道为什么，出度似乎不好维护，但是似乎入度比较好维护。

然后可以把四种操作转化成如下维护：（用 表示初始状态的入度， 表示当前入度）

  1. 断边 ；
  2. 断点 ；
  3. 连边 ；
  4. 复点 。

这样的话，如果 ，则绝对 恒成立。

但是，并不是每一个 都对应着 ，这是显然的。那我们可以考虑用另外一种思路来让入度和出度的维护同步，考虑权值哈希。

给每一个点随机上一个权值，记作 ，然后定义权值入度为 ，计算公式 。 表示初始图的权值入度。重新设计上述操作：

  1. 断边 ；
  2. 断点 ；
  3. 连边 ；
  4. 复点 。

显然，四种操作都可以用 维护。

然后每次判断 则可判断是否了，这样的话，总体时间复杂度为 。

因为我们随机权值是不同的，且两个相加等于另一个的概率极小，所以可以将其是作为一种状态压缩，作为哈希。

代码极其简洁。

AC 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
// ----- Eternally question-----
// Problem: P8819 [CSP-S 2022] 星战
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8819
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2022-11-14 17:18:55
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int N,M,Q;
ll tar,sum,Val[MAXN],r[MAXN],g[MAXN];
std::mt19937 rnd((ll)new char);
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) Val[i]=rnd(),tar+=Val[i];
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);
		r[v]+=Val[u],g[v]+=Val[u];sum+=Val[u];
	}
	read(Q);
	for(int opt,ql,qr;Q--;)
	{
		read(opt);
		if(opt==1) read(ql,qr),r[qr]-=Val[ql],sum-=Val[ql];
		else if(opt==2) read(ql),sum-=r[ql],r[ql]=0;
		else if(opt==3) read(ql,qr),r[qr]+=Val[ql],sum+=Val[ql];
		else read(ql),sum+=g[ql]-r[ql],r[ql]=g[ql];
		puts(sum==tar?"YES":"NO");
	}
	return 0;
}
/*

*/

最觉得输麻了的一件事是：这道题因为西西弗众所周知的原因，直接一行 puts("NO") 能得到 好成绩（甚至就是高一 了）。但是没有关系，靠实力得到的分数，才是真正的分数，这种骗分技巧的话，考场上花个几分钟留意一下就好了。

不可以，总指挥。

数据运输

先说说题意：

给定一个有 个结点的树，点有点权，定义直接连通为两个结点间距离不超过 ，一共 次询问，每一询问一个点对 表示从 到 经过的结点两两直接连通的最小代价。（代价和为经过的结点权值和）

部分分

从部分分考虑走，首先要知道，距离最短不一定代价最短，在经过链的时候，或许可以先跳到链外一个权值小的结点再跳回来，这样的代价或许比直接跳链上代价大的结点代价小。

当 时，我无论如何都会经过 这条链，而点权非负意味着我的点走得越多，代价越大，所以最小代价就是这条路径的点权和，树剖解决即可，得分 。

然后考虑 怎么搞，发现 是可过的，而正好又有 ，我们可以考虑一个 的做法。先说说考场思路（虽然挂了 来着），用 表示从某一定起点 走到 所需的最小代价，我们记 能够直接到达的点集为 ，那么，转移方程就是 ，容易发现，我们从 出发可以遍历整棵树得到答案，同样的，我们也可以通过 出发遍历得到答案（为了保险我就都整了一遍并取较小值），但实际上这样似乎是错误的，因为这样没有办法走回头路，但按照常理而言，这道题应该是可以走回头路的。

然后说说真正的 部分分：考虑建图。对于 的点对，连边 ，并跑点权最短路，每次询问 ，多次询问 ，菊花图可以卡到 。期望且实际得分 。

这两个部分分不重，可以拿到 的好成绩（可惜还是没有 puts("NO"); 多）。

正解

前置芝士：动态树分治、树链剖分、矩阵加速。

因为有 的性质，那就明示了我们可以分开讨论。

对于 ，上面也讲过了。

对于 ，最优方案中只会包含路径上的点，如下图：

摘自洛谷博客——

那这就简单了，记录 表示跳到 点的最小代价，转移： ，这样也有 。

然后考虑 的做法，这样一来，最优解不一定会在链上，而是不断重复更新至毛毛虫的须足里，如下图所示：

摘自洛谷博客——

那么，如果当前结点为 ，路径中的下一个结点为 ，但是走 并不是最优方案，那么我们提取出所有与 相连的结点，这样可以保证下一次操作的时候同样可以跳过 ，甚至 的下一个结点（这是与 不同的地方）。容易发现，包括 在内，我们的行动应当是：从最小值走到次小值或者次小值走到最小值，这是显然的。

我们将 的转移扩展一维，记录 表示为到达了 结点本身或者与其连接的结点，其中 表示当前在其本身， 表示在其链接结点上，再记录 表示其链接结点的权值，那么就有下列转移：

每一次暴力计算的时间复杂度都是 ，会被链卡成 ，均摊时间复杂度为 ，能够得到 的好成绩。

所以我们需要考虑如何去进行优化，在于解决每一次 的时候都是 的时间复杂度这是我们不允许的。

容易发现，这种在树上进行多次 的问题我们曾经遇到过，甚至带修—— ，也就是动态树分治。

那我们就考虑如何用矩乘来进行加速，为了方便，尽管 ，我们也同样构造 的矩阵。

宏定义： 表示从起点到 的距离， 如上，重新定义 为跳到距离 为 的最小代价：

基本结束，这里将 处理为与 相连的权值最小值即可。注意这里的 是广义矩乘的 。

AC 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// ----- Eternally question-----
// Problem: P8820 [CSP-S 2022] 数据传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8820
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2022-12-05 08:15:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10,MAXS=20;
const ll INF=1e18;
struct Matrix
{
	ll mat[3][3];
	inline ll& operator()(int a,int b){ return mat[a][b]; }
}Idt;
inline Matrix operator*(Matrix a,Matrix b)
{
	Matrix c;
	for(int i=0;i<=2;++i)
		for(int j=0;j<=2;++j)
			c(i,j)=INF;
	for(int i=0;i<=2;++i)
		for(int j=0;j<=2;++j)
			for(int k=0;k<=2;++k)
				c(i,j)=std::min(c(i,j),a(i,k)+b(k,j));
	return c;
}
int N,Q,K,Val[MAXN],Num[MAXN],Dep[MAXN];
int Fa[MAXN][MAXS];
Matrix Base[MAXN],Mat[MAXN][MAXS],Rev[MAXN][MAXS];
std::vector<int>Edges[MAXN];
inline bool cmp(int x,int y){ return Val[x]<Val[y]; }
inline void build()
{
	for(int i=0;i<=2;++i)
		for(int j=0;j<=2;++j)
			Idt(i,j)=(i==j?0:INF);
	if(K==1) for(int i=1;i<=N;++i)
	{
		for(int j=0;j<=2;++j)
			for(int k=0;k<=2;++k)
				Base[i](j,k)=INF;
		Base[i](0,0)=Val[i],Base[i](1,1)=Base[i](2,2)=0;
	}
	else if(K==2) for(int i=1;i<=N;++i)
	{
		for(int j=0;j<=2;++j)
			for(int k=0;k<=2;++k)
				Base[i](j,k)=INF;
		Base[i](0,0)=Base[i](0,1)=Val[i];
		Base[i](1,0)=Base[i](2,2)=0;
	}
	else if(K==3) for(int i=1;i<=N;++i)
	{
		for(int j=0;j<=2;++j) Base[i](0,j)=Val[i];
		Base[i](1,0)=Base[i](2,1)=0;
		Base[i](2,0)=Base[i](2,2)=INF;
		Base[i](1,1)=Num[i],Base[i](1,2)=Val[i]+Num[i];
	}
}
inline void dfs(int x,int last)
{
	Fa[x][0]=last,Mat[x][0]=Rev[x][0]=Base[x],Dep[x]=Dep[last]+1;
	for(int i=1;i<MAXS;++i)
	{
		Fa[x][i]=Fa[Fa[x][i-1]][i-1];
		Mat[x][i]=Mat[x][i-1]*Mat[Fa[x][i-1]][i-1];
		Rev[x][i]=Rev[Fa[x][i-1]][i-1]*Rev[x][i-1];
	}
	for(auto v:Edges[x])
	{
		if(v==last) continue;
		dfs(v,x);
	}
}
inline Matrix getLca(int x,int y)
{
	Matrix s1=Idt,s2=Idt;
	if(Dep[y]>Dep[x]) s2=Base[y],y=Fa[y][0];
	for(int i=MAXS-1;i>=0;--i) if(Dep[Fa[x][i]]>=Dep[y])
		s1=Rev[x][i]*s1,x=Fa[x][i];
	if(x==y) return s2*Base[x]*s1;
	for(int i=MAXS-1;i>=0;--i) if(Fa[x][i]!=Fa[y][i])
		s1=Rev[x][i]*s1,s2=s2*Mat[y][i],x=Fa[x][i],y=Fa[y][i];
	return s2*Base[y]*Base[Fa[y][0]]*Base[x]*s1;
}
inline ll solve(int x,int y)
{
	if(x==y) return Val[x];
	if(Dep[x]<Dep[y]) std::swap(x,y);
	Matrix res=getLca(Fa[x][0],y);
	Matrix now=Idt;
	if(K<=2) now(0,0)=Val[x];
	else now(0,0)=Val[x],now(0,1)=Val[x]+Num[x];
	res=res*now;
	return res(0,0);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q,K);
	for(int i=1;i<=N;++i) read(Val[i]);
	for(int i=2,u,v;i<=N;++i)
	{
		read(u,v);
		Edges[u].push_back(v),Edges[v].push_back(u);
	}
	for(int i=1;i<=N;++i) std::sort(Edges[i].begin(),Edges[i].end(),cmp);
	for(int i=1;i<=N;++i) Num[i]=Val[Edges[i][0]];
	build(),dfs(1,0);
	for(int qs,qe;Q--;)
	{
		read(qs,qe);
		write(solve(qs,qe),'\n');
	}
	return 0;
}
/*

*/
相关文章