CodeChef 2020 November Challenge - Scalar Product Tree (莫队)

题目大意：给定一棵根为1的树，每个点有权值$A_i$，每个点按照其从根开始的路径记录下来一串数$(A_1,\cdots,A_u)$构成一个向量$v_u$

每次查询两个点$(x,y)$，查询$v_x\cdot v_y$

由于向量点积是对位相乘的，不好用数据结构维护

考虑用一个序列描述$\text{dfs}$遍历树时每个点入栈出栈的过程，扫描一段前缀即可得到遍历到每个点时$\text{dfs}$栈的情况，也就得到了题目指定的向量

每次查询两个点$x,y$，那么就是查询了两段前缀，用莫队维护两个前缀指针的移动，同时维护每个深度上两个前缀对应的值以及这些值的乘积即可

复杂度为$O(n\sqrt n)$

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
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=6e5+10,P=1e9+7;

int n,m;
struct Edge{
	int to,nxt;
}e[N];
int head[N],ecnt;
void AddEdge(int u,int v) {
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}
int id[N],dfn;

typedef unsigned U;
U A[N];
int L[N],K[N]; // L,K维护括号序列，L为编号,K为左括号还是右括号
U Sum,Ans[N];
int dep[N];

void dfs(int u,int f) {
	L[id[u]=++dfn]=u,K[dfn]=1;
	dep[u]=dep[f]+1;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
	}
	L[++dfn]=u,K[dfn]=-1;
}

int len;
struct Que{
	int l,r,id;
	bool operator < (const Que __) const {
		if(l/len!=__.l/len) return l/len<__.l/len;
		return ((l/len)&1)?r<__.r:r>__.r;
	}
} Q[N];

U S[2][N];
void Add(int d,int x,int k) {
	int p=dep[x];
	Sum-=S[d][p]*S[!d][p];
	S[d][p]=k==1?A[x]:0;
	Sum+=S[d][p]*S[!d][p];
}

int main() {
	n=rd(),m=rd();
	rep(i,1,n) A[i]=rd();
	rep(i,2,n) {
		int u=rd(),v=rd();
		AddEdge(u,v),AddEdge(v,u);
	}
	dfs(1,0),len=sqrt(dfn);
	rep(i,1,m) {
		int l=rd(),r=rd();
		l=id[l],r=id[r];
		if(l>r) swap(l,r);
		Q[i]=(Que){l,r,i};
	}
	sort(Q+1,Q+m+1);
	int l=1,r=1;
	Add(0,1,1),Add(1,1,1);
	rep(i,1,m) {
		while(l<Q[i].l) ++l,Add(0,L[l],K[l]);
		while(l>Q[i].l) Add(0,L[l],-K[l]),l--;
		
		while(r<Q[i].r) ++r,Add(1,L[r],K[r]);
		while(r>Q[i].r) Add(1,L[r],-K[r]),r--;
		Ans[Q[i].id]=Sum;
	}
	rep(i,1,m) printf("%u\n",Ans[i]);
}