P3047 [USACO12FEB] Nearby Cows 题解

发表于 分类于 本文字数： 381 阅读时长 ≈ 1 分钟

true
Nearby Cows
USACO 2012 February Gold
提高+ /省选-
#3498db
  • Luogu P3047

简述一下题意，题目要求我们对于每一个点求出距离其不超过 $k$ 的点的点权和。

操作很简单，我们只需要开一个DP数组，记录下来每一个点与其距离为 $j \in \{ j|[0,k] \}$ 的点权和即可。

首先我们DFS一遍，记录下来每一个点子树中与其距离为 $j \in \{ j|[0,k] \}$ 的点权和：

第一遍DFS
1
2
3
4
5
6
7
8
9
10
11
void dfs1(int p, int fa)
{
    f[p][0] = w[p];
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        dfs1(e[i], p);
        for(int j = 0; j < k; j++)
            f[p][j + 1] += f[e[i]][j];
    }
}

然后考虑其祖先节点对其的影响。

我们通过再一次的DFS来统计影响，所以我们只需要计算该节点的父亲对其的影响即可。

举个例子：
我们现在节点 $x$ 统计答案，其父亲为 $y$。
对于每一个与 $y$ 相距 $j \in \{ j|[0,k-1] \}$ 的节点，其与 $x$ 的距离为 $j+1$。

根据这个我们可以统计出 $y$ 对 $x$ 的影响，然后就可以得到答案了。

第二遍DFS
1
2
3
4
5
6
7
8
9
10
11
12
void dfs2(int p, int fa)
{
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        for(int j = k; j >= 2; j--)
            f[e[i]][j] -= f[e[i]][j - 2];
        for(int j = 0; j < k; j++)
            f[e[i]][j + 1] += f[p][j];
        dfs2(e[i], p);
    }
}

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010, M = N << 1;
int n, m;
int k;
int h[N], e[M], ne[M], idx;
int w[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int f[N][30];
void dfs1(int p, int fa)
{
    f[p][0] = w[p];
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        dfs1(e[i], p);
        for(int j = 0; j < k; j++)
            f[p][j + 1] += f[e[i]][j];
    }
}
void dfs2(int p, int fa)
{
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        for(int j = k; j >= 2; j--)
            f[e[i]][j] -= f[e[i]][j - 2];
        for(int j = 0; j < k; j++)
            f[e[i]][j + 1] += f[p][j];
        dfs2(e[i], p);
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)
    {
        int sum = 0;
        for(int j = 0; j <= k; j++)sum += f[i][j];
        printf("%d\n", sum);
    }
    return 0;
}