『FLA - III』Anxiety

ScaredQiu · 2024-07-14 18:11:20 · 题解

完美二叉树

测试点 1

总共有 3 个节点，直接分讨。

测试点 2 \sim 3

注意到 2^{10}=1024，树上的节点至多 1023 个。

建树，对于每个询问暴力遍历整棵树并标记哪些节点和 x 的距离不超过 k，哪些节点和 y 的距离不超过 k，然后枚举节点计算答案。

时间复杂度 O(2^nm)。

测试点 4 \sim 5

树上节点至多有 2^{18}-1=262143 个。

注意到 k_i \leq 5，所以和某个节点的距离不超过 k_i 的节点不会太多。

具体有多少呢？首先对于给定节点 x，它自己肯定满足要求（距离为 0），如果 x 既不是叶子节点也不是根节点，它就一定有 3 个相邻节点（距离为 1），这 3 个相邻节点既不是叶子节点也不是根节点的话，它们每个节点就也有 3 个相邻节点，排除掉 x 之后它们每个节点都能贡献 2 个新的节点（距离为 2）...

可以得到满足条件的节点数量不超过 1+3+3 \times 2+3 \times 2^2+3 \times 2^3+3 \times 2^4=94 个，询问时暴力遍历的效率可以接受。

对于第 i 次询问，先从节点 x_i 开始遍历，标记所有与 x_i 距离不超过 k_i 的节点；然后从节点 y_i 开始遍历，遇到有标记的节点就将其计入答案。注意清空标记时应当只清空被标记的节点，否则时间复杂度可能退化。笔者的做法是再从 x_i 遍历一次并取消被遍历到的节点的标记。

这里认为回答一次询问的时间复杂度为 O(1)，总体时间复杂度 O(2^n+m)。

这个做法能通过测试点 1 \sim 5 并获得 50 分，注意答案可能超出 int 范围。

#include<bits/stdc++.h>
using namespace std;
int n,m,lim,w[300'000];
vector<int> v[300'000];
bool on[300'000];
long long ans;
void dfs(int x,int las,int step,int uim,function<void(int)> fun){
    fun(x);
    if(step<uim) for(int i:v[x]) if(i!=las) dfs(i,x,step+1,uim,fun);
}
long long query(int x,int y,int k){
    ans=0ll;
    dfs(x,0,0,k,[&](int x)->void{on[x]=1;});
    dfs(y,0,0,k,[&](int x)->void{ans+=on[x]*w[x];});
    dfs(x,0,0,k,[&](int x)->void{on[x]=0;});
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m,lim=(1<<n)-1;
    for(int i=1;i<=lim;i++) cin>>w[i];
    for(int i=2;i<=lim;i++) v[i].push_back(i/2),v[i/2].push_back(i);
    for(int i=1;i<=m;i++){
        static int x,y,k;
        cin>>x>>y>>k;
        cout<<query(x,y,k)<<'\n';
    }
    return 0;
}

测试点 6 \sim 7

现在尝试将问题转化，举个例子：询问和节点 8,14 的距离都不超过 5 的节点权值和。

这等价于询问所有和节点 1 的距离不超过 2 的节点权值和。

为啥？因为节点 1 到节点 8,14 的距离相等，是路径中点。对于节点 2 子树中的节点，它们与节点 14 的距离肯定比与节点 8 的距离大，所以只要这些节点与节点 14 的距离符合要求，它们就一定符合要求。节点 3 子树中的节点同理，只要它们与节点 8 的距离符合要求，也就一定符合要求。

又因为节点 1 到节点 8,14 的距离相等（3），所以只用计算和节点 1 的距离不超过 5-3=2 的节点权值和。

再来一个例子：询问和节点 5,13 的距离都不超过 4 的节点权值和。

这等价于询问所有和节点 1,3 形成的连通块的距离不超过 1 的节点权值和。转化方式同上，由于路径上的节点有偶数个计算过程会复杂一些。

现在尝试利用 w_i=1 的条件，注意到给定的树是一棵完美二叉树，所以当节点 x 的子树中存在与其距离为 k 的节点时，它子树内与节点 x 距离不超过 k 的节点权值和为 2^k-1。

又因为完美二叉树的性质很好，从任意节点向上枚举到根节点的时间复杂度为 O(n)，可以一边向上枚举一边计算答案，具体实现见文末代码。

时间复杂度 O(2^n+nm)。

另外由于 w_i=1，本质不同的询问只有 O(n^3) 个，可能存在其他的做法。

测试点 8 \sim 10

沿用上一个做法，预处理节点 x 的子树中与其距离不超过 k 的节点权值和。因为完美二叉树的性质很好甚至不用把树建出来。计算答案时很可能需要当前节点兄弟的信息，因为完美二叉树的性质，节点 x 的兄弟就是 x \oplus 1（\oplus 表示异或），这是容易的。

时间复杂度 O(n2^n+nm)。

#include<bits/stdc++.h>
using namespace std;
long long s[20][300'000];
int n,m,lim;
void dfs(int x){//预处理节点子树权值和
    if(x*2>lim){
        for(int i=1;i<=n;i++) s[i][x]=s[0][x];
        return;
    }
    dfs(x*2),dfs(x*2+1);
    for(int i=1;i<=n;i++) s[i][x]=s[0][x]+s[i-1][x*2]+s[i-1][x*2+1];
}
long long query(int x,int y,int k){
    static int xi,yi,mid,cnt[2],a[2][40];
    static long long ret;
    xi=0,yi=1,cnt[0]=0,cnt[1]=0;
    while(x!=y){
        if(x<y) swap(x,y),swap(xi,yi);
        a[xi][++cnt[xi]]=x,x/=2;
    }
    a[xi][++cnt[xi]]=x;
    for(int i=cnt[yi];i>=1;i--) a[xi][++cnt[xi]]=a[yi][i];
    k-=cnt[xi]/2;
    if(k<0) return 0ll;
    if(cnt[xi]%2==1){//存在唯一的路径中点
        mid=a[xi][cnt[xi]/2+1];
        ret=s[min(k,n)][mid];
    }
    else{//不存在路径中点需要处理的东西更多
        mid=max(a[xi][cnt[xi]/2],a[xi][cnt[xi]/2+1]);
        ret=s[min(k,n)][mid];
        if(k>=1) ret+=s[min(k-1,n)][mid^1];
        mid/=2,ret+=s[0][mid];
    }
    for(int i=1;i<=k&&mid!=0;i++){//向上枚举
        if(k-i>=1) ret+=s[min(k-i-1,n)][mid^1];
        mid/=2,ret+=s[0][mid];
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m,lim=(1<<n)-1;
    for(int i=1;i<=lim;i++) cin>>s[0][i];
    dfs(1);
    for(int i=1;i<=m;i++){
        static int x,y,k;
        cin>>x>>y>>k;
        cout<<query(x,y,k)<<'\n';
    }
    return 0;
}