【LG3647】[APIO2014]连珠线

题面

题解

首先考虑一下蓝线连起来的情况，一定是儿子-父亲-另一个儿子或者是儿子-父亲-父亲的父亲。

而因为一开始只有一个点在当前局面上，将一条红边变为两条蓝边也只能在一对有父子关系的点之间加，所以第一种“儿子-父亲-另一个儿子”的情况实际上是不存在的。

假设我们当前已经选定根节点，设\(f[i][0/1]\)表示当前位于以\(i\)为根的子树\(i\)不作为/作为中转点(即中间的父亲节点)的最大答案。

那么有转移：

\(f[i][0]=\sum_{j\in son_i} max(f[j][0],f[j][1]+cost_{i,j})\)

钦定一个儿子连上来，得到另一部分的转移：

\(f[i][1]=max_{j\in son_i}\{f[i][0]-max(f[j][0],f[j][1]+cost_{i,j})+f[j][1]+cost_{i,j}\}\)

因为根在哪个位置会使我们的情况受到影响，考虑换根。

令\(g[i][j][0/1]\)表示当前\(i\)不考虑\(j\)这个儿子和作不作为中转点的最大答案。

那么\(g[i][j][0]\)显然为\(f[i][0]-max(f[j][0],f[j][1]+cost_{i,j})\)。

\(g[i][j][1]\)稍微麻烦一些，需要记录转移上来的\(max(f[j][0],f[j][1]+cost_{i,j})+f[j][1]+cost_{i,j}\)最大及次大值，对于从最大值转移上来的儿子，即为次大值的贡献，否则为最大值的贡献。

然后因为这个\(g\)不能直接开数组，所以用\(vector\)代替。

有这个东西就可以偷税的换根了，换根过程详见代码。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int INF = 2e9;

const int MAX_N = 2e5 + 5;

struct Graph { int to, cost, next; } e[MAX_N << 1];

int fir[MAX_N], e_cnt;

void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }

void Add_Edge(int u, int v, int w) { e[e_cnt] = (Graph){v, w, fir[u]}, fir[u] = e_cnt++; }

int N, fa[MAX_N];

int f[MAX_N][2], cost[MAX_N];

vector<int> g[MAX_N][3], son[MAX_N], mx[MAX_N];

void dfs(int x) {

	f[x][0] = 0, f[x][1] = -INF;

	for (int i = fir[x]; ~i; i = e[i].next)

		if (e[i].to != fa[x]) fa[e[i].to] = x, dfs(e[i].to);

	for (int i = fir[x]; ~i; i = e[i].next) {

		int v = e[i].to; if (v == fa[x]) continue;

		son[x].push_back(v), cost[v] = e[i].cost;

		f[x][0] += max(f[v][0], f[v][1] + e[i].cost);

	}

	int m1 = -INF, m2 = -INF;

	for (int i = fir[x]; ~i; i = e[i].next) {

		int v = e[i].to; if (v == fa[x]) continue;

		int val = f[v][0] + e[i].cost - max(f[v][0], f[v][1] + e[i].cost);

		f[x][1] = max(f[x][1], f[x][0] + val);

		if (val > m1) m2 = m1, m1 = val;

		else if (val > m2) m2 = val;

	} 

	for (int i = fir[x]; ~i; i = e[i].next) {

		int v = e[i].to; if (v == fa[x]) continue;

		g[x][0].push_back(f[x][0] - max(f[v][0], f[v][1] + e[i].cost));

		int val = f[v][0] + e[i].cost - max(f[v][0], f[v][1] + e[i].cost);

		if (val == m1) g[x][1].push_back(g[x][0].back() + m2), mx[x].push_back(m2);

		else g[x][1].push_back(g[x][0].back() + m1), mx[x].push_back(m1);

	}

}

int ans = 0;

void rdfs(int x) {

	for (int i = 0; i < (int)son[x].size(); i++) {

		f[x][0] = g[x][0][i], f[x][1] = g[x][1][i];

		if (fa[x]) {

			f[x][0] += max(f[fa[x]][0], f[fa[x]][1] + cost[x]);

			f[x][1] = f[x][0] + max(mx[x][i], f[fa[x]][0] + cost[x] - max(f[fa[x]][0], f[fa[x]][1] + cost[x]));

		}

		ans = max(ans, f[son[x][i]][0] + max(f[x][0], f[x][1] + cost[son[x][i]]));

		rdfs(son[x][i]);

	}

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	clearGraph();

	N = gi();

	for (int i = 1; i < N; i++) {

		int u = gi(), v = gi(), w = gi();

		Add_Edge(u, v, w);

		Add_Edge(v, u, w);

	}

	dfs(1);

	ans = f[1][0];

	rdfs(1);

	printf("%d\n", ans);

    return 0;

}

巴特西

【LG3647】[APIO2014]连珠线

【LG3647】[APIO2014]连珠线

题面

题解

代码

最新文章

热门文章