题解：P13875 [蓝桥杯 2024 省研究生组] 植物生命力

· · 题解

P13875 [蓝桥杯 2024 省研究生组] 植物生命力 - 题解

思路：

看起来不太可做，但我们可以注意到题目中有这样一句话：对于所有的测试用例，1 \le a_i \le n，a_1, a_2, \ldots, a_n 互不相同。这说明所有的节点权值组成了一个 1 到 n 的排列，这是一个良好的性质。

对于这道题，一个显然的思路就是：对于所有的 i 查询子树内小于 a_i 的权值个数，再减去子树内被 a_i 整除的权值个数，前者需要使用可持久化线段树才能解决，而后者直接计算也十分困难，所以我们考虑另一个思路：计算每一个节点对答案产生的贡献，由此产生了一个显然的算法：当遍历到该节点时将这个节点权值插入线段树，查询线段树内插入的权值有多少个比该权值大，再减去线段树内是该权值整数倍的权值，然后从线段树中删除该节点。线段树的部分容易解决，而减去整数倍的部分却几乎不可做，似乎陷入了僵局。但此时回到开头提到的性质：节点权值是一个 1 到 n 的排列，那么我们就可以直接对每一个权值枚举它的整数倍是否在线段树中，对于权值 1，要枚举 \frac{n}{1} 次；对于权值 2，要枚举 \frac{n}{2} 次，以此类推，对于整棵树，总共要枚举：

\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}

这么多次，即 n\ln{n} 次，可以通过此题。

一些显然的优化：可以用树状数组代替线段树，以减小常数；把权值插入树状数组的同时打标记，这样在枚举整数倍的时候可以做到 O(1) 查询而无需在树状数组上查询。

代码：

vector<int> mp[100005];
int w[100005];
bool vis[100005];
int n,rt;
long long ans;
int c[100005];
void add(int x,int v)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=v;
}
int qry(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))    res+=c[x];
    return res;
}
void dfs(int u,int f)
{
    vis[w[u]]=1;
    add(w[u],1);
    for(int v:mp[u])
    {
        if(v==f)    continue;
        dfs(v,u);
    }
    for(int i=2;i*w[u]<=n;i++)
        ans-=vis[i*w[u]];
    ans+=qry(n)-qry(w[u]);
    vis[w[u]]=0;
    add(w[u],-1);
}
char QQ,coin;
decltype(QQ+coin) main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>rt;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(rt,0);
    cout<<ans<<"\n";
    return ~(-1);
}