题目链接

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;

}

CF 633 F. The Chocolate Spree 树形dp的相关教程结束。