树可以DP的天然优势就是子树自成一个子问题,只考虑在节点处合并即可。
\(f[i][0]\)表示这个点不选择
\(f[i][1]\)表示这个点选择
代码:
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 6000 + 7;
vector<int> g[maxN];
int a[maxN];
int f[maxN][2];
bool vis[maxN];
void dfs(int now) {
f[now][1] = a[now];
for(int i = 0;i < g[now].size();++ i) {
int v = g[now][i];
dfs(v);
f[now][1] += f[v][0];
f[now][0] += max(f[v][1] , f[v][0]);
}
}
int main() {
int n = gi();
rep(i , 1, n) a[i] = gi();
rep(i , 1, n - 1) {
int v = gi(),u = gi();
g[u].push_back(v);
vis[v] = true;
}
int root;
rep(i , 1, n) if(!vis[i]) root = i;
dfs(root);
printf("%d",max(f[root][0] , f[root][1]));
return 0;
}
士兵关系可以形成一张基环森林。
考虑断环上的一边,对顶点(u,v)分别树形DP
\(f[i][0]\)表示这个点不选择
\(f[i][1]\)表示这个点选择
\(f[i][1] = \sum_{v \in son_i}f[v][0]\)
\(f[i][0] = \sum_{v \in son_i}max(f[v][0],f[v][1])\)
那么答案是max(f[u][0],f[v][0])
因为u跟v中必定有一个不选择。
还有一个问题就是为什么不枚举环上的所有边进行断边。
因为我们记录的答案已经含有所以可能的答案
没调过的代码:
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 1e6 + 7;
struct Node {
int v , nex;
}Map[maxN << 1];
int head[maxN] , num;
bool vis[maxN];
int a[maxN];
void add_Node(int u , int v) {
Map[++ num] = (Node) {v , head[u]};
head[u] = num;
}
int f[maxN][2];
bool cvis[maxN], vis2[maxN];
void find(int now , int fa) {
vis[now] = true;
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
if(vis[v]) {
cvis[now] = true;
return;
}
find(v , now);
if(cvis[v]) cvis[now] = true;
}
return ;
}
void dp(int now,int be,int end) {
vis2[now] = true;
f[now][1] = a[now];
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(now == be && v == end) continue;
if(now == end && v == be) continue;
if(vis2[v]) continue;
dp(v , be, end);
f[now][1] += f[v][0];
f[now][0] += max(f[v][0] , f[v][1]);
}
return ;
}
int main() {
int n = gi();
rep(i , 1, n) {
a[i] = gi();int x = gi();
add_Node(i , x);
add_Node(x , i);
}
int ans = 0;
rep(i , 1, n) {
if(!vis2[i]) {
int x , y;
find(i,0);
for(int j = i;j >= 1;-- j) {
if(vis2[j]) break;
if(cvis[j]) {
for(int now = head[j];now;now = Map[now].nex) {
int v = Map[now].v;
if(cvis[v]) {
x = j;y = v;
break;
}
}
}
}
memset(f , 0, sizeof(f));
dp(x , x, y);
memset(vis2,0,sizeof(vis2));
memset(f , 0, sizeof(f));
dp(y , x, y);
ans += max(f[x][0] , f[y][0]);
}
}
printf("%d",ans);
return 0;
}
f(x) 表示让 x 子树内的叶子到 x 的距离相同,至少要多少次操作。
g(x) 表示 x 子树内的叶子到 x 的最长距离。
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define rep(i , x, y) for(int i = x;i <= y;++ i)
#define sep(i , x, y) for(int i = x;i >= y;-- i)
#define PII pair<int,int>
#define mk make_pair
#define ll long long
#define fi first
#define se second
inline int gi() {
int x = 0, f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 5e5 + 7;
struct Node {
int v , nex, w;
}Map[maxN << 1];
int head[maxN] , num;
void add_Node(int u , int v, int w) {
Map[++ num] = (Node) {v , head[u], w};
head[u] = num;
}
ll f[maxN] , g[maxN];
void dfs(int now , int fa) {
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
dfs(v , now);
g[now] = max(g[v] + Map[i].w , g[now]);
}
for(int i = head[now];i;i = Map[i].nex) {
int v = Map[i].v;
if(v == fa) continue;
f[now] += f[v] + (g[now] - g[v] - Map[i].w);
}
return ;
}
int main() {
int n = gi();
int root = gi();
for(int i = 1;i < n;++ i) {
int u = gi(),v = gi(),w = gi();
add_Node(u , v, w);
add_Node(v , u, w);
}
dfs(root , 0);
printf("%lld",f[root]);
return 0;
}
叛徒一定是在叶子结点,叛徒一定是一颗子树的全部结点。
原文:https://www.cnblogs.com/gaozhuoyuan/p/11674486.html