当前位置:网站首页>P3047 [usaco12feb]nearby cows g (tree DP)
P3047 [usaco12feb]nearby cows g (tree DP)
2022-07-06 07:42:00 【eva_ can(not)survive】
[USACO12FEB]Nearby Cows G - Luogu https://www.luogu.com.cn/problem/P3047 A very interesting tree dp
We can set the State f【i】【j】, i Is the current root ,j The distance is j Point weight sum of time
First we can take 1 Run for the root dfs, Will be with i The point weight and record of the subtree for the root, that is, update the father with the son , here 1 It must be over , We can start from 1 Start running dfs Use the father to renew the son .
#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;
}
边栏推荐
- word怎么只删除英语保留汉语或删除汉语保留英文
- Methods for JS object to obtain attributes (. And [] methods)
- [非线性控制理论]9_非线性控制理论串讲
- leecode-C语言实现-15. 三数之和------思路待改进版
- Typescript function definition
- [MySQL learning notes 29] trigger
- [dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
- How to delete all the words before or after a symbol in word
- qt颜色与字符串、uint相互转换
- Type of data in energy dashboard
猜你喜欢
Redis builds clusters
Opencv learning notes 9 -- background modeling + optical flow estimation
智能终端设备加密防护的意义和措施
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
学go之路(一)go的基本介绍到第一个helloworld
Simulation of Michelson interferometer based on MATLAB
NiO programming introduction
octomap averageNodeColor函数说明
Solution: système de surveillance vidéo intelligent de patrouille sur le chantier
Typescript interface and the use of generics
随机推荐
Full Score composition generator: living on code
TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
Rust language - receive command line parameter instances
QT color is converted to string and uint
49. Sound card driven article collection
Ble of Jerry [chapter]
word设置目录
Jerry's ad series MIDI function description [chapter]
CF1036C Classy Numbers 题解
Google may return to the Chinese market after the Spring Festival.
[cf gym101196-i] waif until dark network maximum flow
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
Luogu p1836 number page solution
Redis list detailed explanation of character types yyds dry goods inventory
Fundamentals of C language 9: Functions
Generator Foundation
Redis builds clusters
word中如何删除某符号前面或后面所有的文字
Typescript void base type