CF1806E Tree Master

Description

https://www.luogu.com.cn/problem/CF1806E

Solution

水群的时候发现的很有意思的题，一眼只能想到树分块和莫队。

首先考虑根号分治，对深度是没有前途的，转而对每层节点数分治：

• 当前层节点数 $x < \sqrt n$，总共有 $\dbinom{x}{2}=O(x^2)$ 种本质不同的询问，所以 $<\sqrt n $ 的总的本质不同的询问有 $\sum x_i^2\le (\sum x_i)\times (\max x_i )\le O(n\sqrt n)$。
• 对于 $x\ge \sqrt n$，这样的层只有 $O(\sqrt n )$ 个，每次询问查询一次就是 $O(q\sqrt n)$。

为了避免本质相同的询问带来的影响，考虑记忆化搜索。只需要把节点数 $<\sqrt n$ 的记下来即可，可以避免使用哈希表或者 map。

复杂度 $O((n+q)\sqrt n)$。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 110005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,q,a[maxn],deep[maxn],fa[maxn];
int f[maxn][505],t[maxn],id[maxn];
const int base=500;
int dfs(int x,int y) {
	if (!x) return 0;
	if (t[deep[x]]<=base) {
		if (f[x][id[y]]!=-1) return f[x][id[y]];
		else return f[x][id[y]]=f[y][id[x]]=a[x]*a[y]+dfs(fa[x],fa[y]);
	}
	else return a[x]*a[y]+dfs(fa[x],fa[y]);
}
signed main(void){
	int i,x,y;
	memset(f,-1,sizeof(f));
	read(n);read(q);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=2;i<=n;i++) read(fa[i]);
	for (i=1;i<=n;i++) {
		deep[i]=deep[fa[i]]+1;
		id[i]=t[deep[i]]++;
	}
	while (q--) {
		read(x);read(y);
		printf("%lld\n",dfs(x,y));
	}
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i