Codeforces #858 : Div2 E. Tree Master

変な解法。
https://codeforces.com/contest/1806/problem/E

問題

根付き木が与えられる。
各点には整数値が設定されている。

以下のクエリに答えよ。
同じ深さの2点u,vが指定される。
それぞれ根頂点までのパス上の頂点の設定値を並べたベクトルを作り、その内積を答えよ。

解法

部分的にメモ化しつつ愚直に解く。
以下の解法では、深さ16毎にメモ化している。

int N,Q;
ll A[101010];
int P[101010];
int D[101010];
unordered_map<int,ll> memo[101010];
vector<int> X,Y;
vector<ll> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,N) {
		scanf("%d",&x);
		A[i]=x;
	}
	FOR(i,N-1) {
		scanf("%d",&x);
		P[i+1]=x-1;
		D[i+1]=D[x-1]+1;
	}
	memo[0][0]=1LL*A[0]*A[0];
	
	while(Q--) {
		scanf("%d%d",&x,&y);
		x--,y--;
		if(x>y) swap(x,y);
		X={x};
		Y={y};
		V.clear();
		
		ll ret=0;
		while((D[x]&15)||memo[x].count(y)==0) {
			V.push_back(1LL*A[x]*A[y]);
			x=P[x];
			y=P[y];
			if(x>y) swap(x,y);
			X.push_back(x);
			Y.push_back(y);
		}
		V.push_back(memo[x][y]);
		ll sum=0;
		while(V.size()) {
			x=X.back();
			y=Y.back();
			sum+=V.back();
			if((D[x]&15)==0) memo[x][y]=sum;
			X.pop_back();
			Y.pop_back();
			V.pop_back();
		}
		cout<<sum<<"\n";
	}
	
	
	
}

まとめ

想定解とはちょっと違った様子。