P15061 琥峪枫 题解

FFTotoro · 2026-01-26 16:03:22 · 题解

先全问一遍 (x,1) 求和，可以求出 S=3\sum\limits_{u=1}^na_u-2\sum\limits_{u\in\text{leaves}}a_u-a_{\mathrm{root}} 的值，再询问所有 (x,h+1) 可以得到 \mathrm{root} 与其两个儿子结点 l,r，再询问这三个点的 (x,h) 可以把 S 的第二项消掉，S 的第三项 a_{\mathrm{root}} 相当于 (l,1)+(r,1)-(\mathrm{root},2)，至此就可以求出答案。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ask(int u,int d);
ll solve(int id,int h){
  int n=(1<<h)-1;
  vector<ll> d1(n);
  for(int i=0;i<n;i++)
    d1[i]=ask(i+1,1);
  vector<int> t2;
  for(int i=1;i<n;i++)
    if(!ask(i+1,h+1))t2.emplace_back(i);
  if(t2.size()<3)t2.emplace_back(0);
  vector<ll> v2(3);
  int rt=-1;
  ll c0=0;
  for(int i=0;i<3;i++)
    if(!(v2[i]=ask(t2[i]+1,h)))rt=t2[i];
    else c0+=d1[t2[i]];
  ll c1=v2[0]+v2[1]+v2[2]<<1;
  return (accumulate(d1.begin(),d1.end(),0ll)+c1+(c0-ask(rt+1,2))/2)/3;
}