CF1806E 题解

题目大意

给你一棵树，然后定义一个函数 $ f(x,y) $，接下来给你 $ q $ 组询问 \(x_{i},y_{i}\)，让你求每一次的 $ f(x_{i},y_{i})$。

分析

首先我们尝试根据这个函数的定义暴力求值，代码实现如下。

ll BFquery(int g,int h) {
    if(!g) return 0;
    return 1ll*a[g]*a[h]+BFquery(p[g],p[h]);
}

每次调用这个函数即可。时间复杂度是 $ O(nq) $,不足以通过此题。

于是我们来分析题目中用粗体标注的一个条件：每次给出的 \(x_{i}\) 和 \(y_{i}\)，它们深度相同。

这就表明一个点的权值只会和与它处于同一深度的任意一个点相乘，这就减少了相乘点对的组数，也增加了它们出现的次数，会导致我们多次计算同一个 \(f(x,y)\) 的值，增大时间复杂度。

对于这个问题，我们可以尝试用类似记忆化搜索的方法来解决，但是为了不超过空间限制，也不能全部记录，即对于每一组 \(x,y\)，我们可以设一个值 \(B\)，即在不记录答案的情况下，最多计算 \(B\) 次。对于余下的计算，每次的值都会被存储在一个 map 中，这样时间复杂度可以优化至近似 \(O(Bq)\)。

而另外一种方法，存储深度较大的部分而不存储深度较小的部分，目前没有找到这方面正确的做法，如果以后找到我会补上。

下面是代码。

int n,q,a[100005]={},p[100005]={},d[100005]={},rp[100005]={},f,s,cnt=0,P;
ll res;
vector<int> v[100005],op[100005];
map<ll,ll> mp;
const int M=100005,B=500;

ll BFquery(int g,int h) {
    if(!g) return 0;
    if(g>h) swap(g,h);
    if(mp[1ll*g*M+h]!=0) return mp[1ll*g*M+h];
    else {
        mp[1ll*g*M+h]=1ll*a[g]*a[h]+BFquery(p[g],p[h]);
        return mp[1ll*g*M+h];
    }
}

void wk() {
    read(n),read(q);
    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=2,x;i<=n;++i) {
        read(x);
        v[x].emplace_back(i);
        p[i]=x;
    }
    while(q--) {
        read(f),read(s);
        if(f>s) swap(f,s);
        res=0;
        P=B;
        while(f && s && P>0) {
            res+=1ll*a[f]*a[s];
            f=p[f];
            s=p[s];
            --P; 
        }
        if(f) res+=BFquery(f,s);
        writeln(res);
    }
}