【换根DP】洛谷 P3047 [USACO12FEB]Nearby Cows G
2022-03-31 21:46:00
# ACM
题链
https://www.luogu.com.cn/problem/P3047
题解
- 给你一棵 n 个点的树，点带权，对于每个节点求出距离它不超过 k 的所有节点权值和 m_i;
- 假设以 1 为根节点
- w[u] 表示 节点 u 的权值
- 设 g[u][k] 表示 以 u 为根节点的子树范围为 k 的节点权值和 :
- g[u][0] = w[u];
- g[u][k] = g[u][0] + sum(g[vi][k-1]); (k >= 1)
- sum 为求和，vi 为 u 的孩子节点
- 设 f[u][k] 表示 以 u 为中心，范围为 k 的所有节点权值和 :
- f[u][0] = g[u][0];
- f[1][k] = g[1][k];
- f[v][k] = g[v][k] + ( f[u][k-1] + g[v][k-2] ); (k >= 2)
- f[v][k] = g[v][k] + ( f[u][k-1] ); (k == 1)
代码
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
| #include <bits/stdc++.h>
using namespace std;
#define MS 100009
int n, m, k;
vector<int > vc[MS];
int g[MS][22];
int ans[MS][22];
void dfs1(int u, int f, int range){
g[u][range] = g[u][0];
for(auto v:vc[u]){
if(v == f) continue;
dfs1(v, u, range);
g[u][range] += g[v][range-1];
}
}
void dfs2(int u, int f, int range){
for(auto v:vc[u]){
if(v == f) continue;
ans[v][range] = g[v][range] + (ans[u][range-1] - (range-2>=0? g[v][range-2] : 0));
dfs2(v, u, range);
}
}
void solve(){
cin >> n >> k;
for(int i=2;i<=n;i++){
int u, v; cin >> u >> v;
vc[u].push_back(v);
vc[v].push_back(u);
}
for(int i=1;i<=n;i++){
int w; cin >> w;
g[i][0] = ans[i][0] = w;
}
for(int i=1;i<=k;i++) dfs1(1, 0, i);
for(int i=1;i<=k;i++) ans[1][i] = g[1][i], dfs2(1, 0, i);
for(int i=1;i<=n;i++) cout << ans[i][k] << "\n";
}
int main(){
ios::sync_with_stdio(false);
int ce = 1;
while(ce--) solve();
return 0;
}
|
2022-03-31 21:46:00
# ACM
