CF 633 F. The Chocolate Spree 树形dp

CF 633 F. The Chocolate Spree 树形dp"/>

CF 633 F. The Chocolate Spree 树形dp

题目链接

CF 633 F. The Chocolate Spree

题解

维护子数答案 子数直径 子数最远点 单子数最长直径 (最长的 最远点+一条链)
讨论转移

代码

#include<vector> 
#include<cstdio> 
#include<algorithm> 
#define gc getchar() 
#define pc putchar 
#define int long long 
inline int read() {int x = 0,f = 1; char c = gc;  while(c < '0' || c > '9') c = gc; while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc; return x * f; 
} 
void print(int x) {if(x >= 10) print(x / 10); pc(x % 10 + '0'); 
}
const int maxn = 100007; 
int val[maxn]; 
struct node { int v,next; 
} edge[maxn << 1]; 
int num = 0,head[maxn]; 
inline void add_edge(int u,int v) { edge[++ num].v = v; edge[num].next = head[u];head[u] = num; 
} 
int n; 
int f[maxn][2]; //0 : 两链之和最大 1 : 直径 
int g[maxn]; //表示以u为根的子树中从u到叶子节点加上另外一条链的最长长度
int h[maxn]; //子数的f[ ][1]的最大值 
int far[maxn]; //最远的叶子节点 
void dfs(int x,int fa) { far[x] = g[x] = f[x][1] = f[x][0] = val[x]; h[x] = 0; for(int i = head[x];i;i = edge[i].next) {  int v = edge[i].v; if(edge[i].v == fa) continue; dfs(v,x); f[x][0] = std::max(f[x][0],f[v][0]); f[x][0] = std::max(f[x][0],f[v][1] + f[x][1]); f[x][0] = std::max(f[x][0],far[x] + g[v]); f[x][0] = std::max(f[x][0],far[v] + g[x]); f[x][1] = std::max(f[x][1],f[v][1]);  f[x][1] = std::max(f[x][1],far[x] + far[v]); g[x] = std::max(g[x],val[x] + g[v]); g[x] = std::max(g[x],far[v] +val[x] + h[x]); g[x] = std::max(g[x],far[x] + f[v][1]); h[x] = std::max(h[x],f[v][1]); far[x] = std::max(far[x],far[v] + val[x]); } 
} 
main() { n = read(); for(int i = 1;i <= n;++ i) val[i] = read(); for(int i = 1;i < n;++ i) {int u = read(), v = read(); add_edge(u,v); add_edge(v,u); } dfs(1,0); print(f[1][0]); return 0; 
} 

转载于:.html