Wuyanru's blog
0%

[CF1806E] Tree Master

发表于 分类于 ，

服了，暴力没卡过去。

CF 评测姬好慢。

题目链接

题意

有一棵 个结点的树，点有点权，根是 。对于两个深度相等的节点 ，定义 ，特别地，。给出 次询问，每次询问 。

题解

考虑对于每一个询问，暴力找父亲，直到找到根。显然时间复杂度是 ，过不了。

但是如果加上一个记忆化，时间复杂度就对了。

证明

假设哈希表的时间复杂度为 。

设深度为 的节点个数为 。

当 时，时间复杂度为 。

因为 ，所以 。

当 时，时间复杂度为 。

因为 ，所以这样的 的数量不会超过 个。

时间复杂度为 。

还有一种不需要哈希表的方式：

对于每一个 的深度，我们进行记忆化，空间复杂度是 。

对于剩下的深度，我们暴力做，这种情况单次询问不会超过 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
template<const int N,const int M>
struct graph
{
    int head[N+5];
    int t[M+5];
    int x[M+5];
    int cntm;
    graph(){ cntm=1;}
    void clear(int n=N)
    {
        cntm=1;
        for(int i=1;i<=n;i++) head[i]=0;
    }
    void ad(int u,int v)
    {
        cntm++;
        t[cntm]=v;
        x[cntm]=head[u];
        head[u]=cntm;
    }
    void add(int u,int v)
    {
        ad(u,v);
        ad(v,u);
    }
    int st(int num){ return head[num];}
    int to(int num){ return t[num];}
    int nx(int num){ return x[num];}
};
graph<100000,100000>g;
ll mem[100001][335];
vc<int>v[100001];
int dep[100001];
int id[100001];
int fa[100001];
int c[100001];
int a[100001];
int n,m;
int sq;
void dfs(int num)
{
    id[num]=c[dep[num]]++,v[dep[num]].push_back(num);
    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        dep[p]=dep[num]+1;
        dfs(p);
    }
}
inline ll get(int x,int y)
{
    if(c[dep[x]]<=sq&&mem[x][id[y]]) return mem[x][id[y]];
    ll ans=get(fa[x],fa[y])+(ll)a[x]*a[y];
    if(c[dep[x]]<=sq) mem[x][id[y]]=ans;
    return ans;
}
int main()
{
    n=read(),m=read();
    for(;(sq+1)*(sq+1)<=n;sq++);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i<=n;i++) g.ad(fa[i]=read(),i);
    dfs(1),mem[1][0]=(ll)a[1]*a[1];
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        printf("%lld\n",get(x,y));
    }
    return 0;
}

感谢观看！