所有代码的开头头文件,宏定义和命名空间如下
#include <bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define ll long long #define CI const int #define RI int #define W while #define gc getchar #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) #define Mt(a,x) memset((a),(x),sizeof(a)) using namespace std; namespace SlowIO { void Readc (char& c) {W (isspace (c = gc ()));} Tp void Read (Ty& x) {char c; int f = 1; x = 0; W (! isdigit (c = gc ())) f = c ^ '-' ? 1 : -1; W (x = (x * 10) + (c ^ 48), isdigit (c = gc ())); x *= f;} Ts void Read (Ty& x, Ar&... y) {Read (x); Read (y...);} } using namespace SlowIO;
P1122 最大子树和
solution
不妨设此无根树的根为 1, 父亲为 0。设 \(dp_i\) 表示以 \(i\) 为根的子树中权值和最大的子树的权值和。
明显的,对于 \(now\) 的一个儿子 \(s\),如果 \(dp_s\le 0\),则不选此子树,否则选择。
转移方程式:\(dp_{now}=\sum\limits_{s\in now}[dp_s>0]dp_s\)。答案为所有 \(dp_i\) 中最大的一个。
PS:记得邻接表大小开两倍。
code
CI N = 3.2e4; int n, D[N + 5];
namespace graph {
int H[N + 5], Nt[N + 5], T[N + 5], C = 0;
void A (int u, int v) {++ C; T[C] = v; Nt[C] = H[u]; H[u] = C;}
} using namespace graph;
void Do (int Nw, int F) {RI i, j; for (i = H[Nw]; i; i = Nt[i]) {if (T[i] == F) continue; Do (T[i], Nw); if (D[T[i]] > 0) D[Nw] += D[T[i]];}}
int main () {
RI i, j; for (Read (n), i = 1; i <= n; ++ i) Read (D[i]); for (i = 2; i <= n; ++ i) {int u, v; Read (u, v); A (u, v); A (v, u);} Do (1, 0);
return printf ("%d\n", *max_element (D + 1, D + n + 1)), 0;
}
标签:now,int,树形,DP,康复训练,Nw,Nt,dp,define
From: https://www.cnblogs.com/ClapEcho233/p/17307309.html