当前位置:网站首页>P3047 [USACO12FEB]Nearby Cows G(树形dp)
P3047 [USACO12FEB]Nearby Cows G(树形dp)
2022-07-06 07:35:00 【eva_can(not)survive】
[USACO12FEB]Nearby Cows G - 洛谷https://www.luogu.com.cn/problem/P3047一个很有趣的树形dp
我们可以设状态f【i】【j】, i为当前根,j为距离为j时的点权和
首先我们可以取1为根跑一遍dfs,将以i为根的子树的点权和记录下即用儿子更新父亲,此时1肯定已经求完了,我们就可以再一次从1开始跑dfs用父亲去更新儿子。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;
int n, k;
int head[MAXN];
int ver[MAXN];
int nxt[MAXN];
int cost[MAXN];
int cnt;
int dep[MAXN];
int dp[MAXN][21];
void add(int x, int y) {
ver[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs1(int p, int fa) {
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
// dep[v] = dep[p] + 1;
dfs1(v, p);
for (int j = 1; j <= k; j++) {
dp[p][j] += dp[v][j - 1];
}
}
}
void dfs2(int p, int fa) {
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
for (int j = k; j >= 2; j--) {
dp[v][j] += dp[p][j - 1] - dp[v][j - 2];
}
dp[v][1] += cost[p];
dfs2(v, p);
}
}
int main() {
scanf("%d %d", &n, &k);
int x, y;
for (int i = 1; i <= n - 1; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) {
scanf("%d", cost + i);
dp[i][0] = cost[i];
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int j = 0; j <= k; j++) {
ans += dp[i][j];
}
printf("%d\n", ans);
}
return 0;
}
边栏推荐
- Games101 Lesson 7 shading 1 Notes
- In the era of digital economy, how to ensure security?
- 杰理之需要修改 gatt 的 profile 定义【篇】
- Wonderful use of TS type gymnastics string
- Le chemin du navigateur Edge obtient
- TypeScript接口与泛型的使用
- Oracle column to row -- a field is converted to multiple rows according to the specified separator
- OpenJudge NOI 2.1 1661:Bomb Game
- Apache middleware vulnerability recurrence
- Supervisor usage document
猜你喜欢
数字IC设计笔试题汇总(一)
Simulation of holographic interferogram and phase reconstruction of Fourier transform based on MATLAB
Compliance and efficiency, accelerate the digital transformation of pharmaceutical enterprises, and create a new document resource center for pharmaceutical enterprises
Go learning --- use reflection to judge whether the value is valid
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
word中如何删除某符号前面或后面所有的文字
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Google may return to the Chinese market after the Spring Festival.
Related operations of Excel
Markdown 中设置图片图注
随机推荐
杰理之蓝牙设备想要发送数据给手机,需要手机先打开 notify 通道【篇】
Ble of Jerry [chapter]
实现精细化生产, MES、APS、ERP必不可少
[computer skills]
Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
In the era of digital economy, how to ensure security?
word中把帶有某個符號的行全部選中,更改為標題
[MySQL learning notes 30] lock (non tutorial)
杰理之AD 系列 MIDI 功能说明【篇】
TypeScript 函数定义
杰理之需要修改 gatt 的 profile 定义【篇】
octomap averageNodeColor函数说明
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
The way to learn go (II) basic types, variables and constants
navicat如何导入MySQL脚本
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
合规、高效,加快药企数字化转型,全新打造药企文档资源中心
GET/POST/PUT/PATCH/DELETE含义
http缓存,强制缓存,协商缓存
解决方案:智慧工地智能巡检方案视频监控系统